{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T19:40:13Z","timestamp":1736106013808,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540610434"},{"type":"electronic","value":"9783540498759"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0027117","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T11:08:23Z","timestamp":1132398503000},"page":"25-50","source":"Crossref","is-referenced-by-count":3,"title":["Randomized parallel algorithms"],"prefix":"10.1007","author":[{"given":"Andrea","family":"Clementi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 D. P.","family":"Rolim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Urland","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"3_CR1","unstructured":"N. Alon and J.H. Spencer: The Probabilistic Method. Wiley-Interscience Publication, 1992."},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, R.J. Anderson: A Random NC Algorithm for Depth First Search. 19th Annual ACM-STOC, 325\u2013334, 1987.","DOI":"10.1145\/28395.28430"},{"issue":"3","key":"3_CR3","first-page":"400","volume":"7","author":"R.J. Anderson","year":"1987","unstructured":"R.J. Anderson: A parallel algorithm for the maximal path problem. Combinatorica 7(3), 400\u2013415, 1987.","journal-title":"Combinatorica"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"L. Babai, Fortnow L. Levin L and M. Szegedy: Checking computation in polylogarithmic time. 23th Annual ACM-STOC 21\u201328, 1991.","DOI":"10.1145\/103418.103428"},{"key":"3_CR5","unstructured":"B. Bollobas: Random Graphs. Academic Press, 1985."},{"key":"3_CR6","unstructured":"D.P. Bovet and P. Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994."},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1090\/dimacs\/022\/02","volume":"22","author":"A. Clementi","year":"1995","unstructured":"A. Clementi, L. Kucera, J. Rolim: A Note on Parallel Randomized Algorithms for Searching Problems\u201d, DIMACS Series in Discrete Mathematics and Theoretical Computer Sciences, American Mathematical Society, 22, 33\u201344, 1995.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Sciences, American Mathematical Society"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"E. Cohen: Polylog-time and near-linear work approximation scheme for undirected shortest paths. 26th Annual ACM-STOC, 16\u201326, 1994.","DOI":"10.1145\/195058.195089"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"D. Coppersmith, P. Raghavan, M. Tompa: Parallel Graph Algorithms that are Efficient on Average. 28th Annual IEEE-FOCS, 260\u2013269, 1987.","DOI":"10.1109\/SFCS.1987.46"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1137\/0205040","volume":"5","author":"L. Csanky","year":"1976","unstructured":"L. Csanky: Fast Parallel Matrix inversion Algorithms. SIAM J. of Computing 5, 618\u2013623, 1976.","journal-title":"SIAM J. of Computing"},{"key":"3_CR11","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erdos","year":"1959","unstructured":"P. Erdos and A. Renyi: On Random Graphs I. Publ. Math. Debrecen 6, 290\u2013297, 1959.","journal-title":"Publ. Math. Debrecen"},{"key":"3_CR12","volume-title":"Flows in Networks","author":"L.R. Ford","year":"1962","unstructured":"L.R. Ford, D.R. Fulkerson: Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962."},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Z. Galil, V. Pan: Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC. 26th Annual IEEE-FOCS, 490\u2013495, 1985.","DOI":"10.1109\/SFCS.1985.33"},{"key":"3_CR14","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey, D.S. Johnson: Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco, 1979."},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/BF01937481","volume":"24","author":"R. K. Ghosh","year":"1984","unstructured":"R. K. Ghosh, G. P. Bhattacharjee: A parallel search algorithm for directed acyclic graphs. BIT 24, 134\u2013150, 1984.","journal-title":"BIT"},{"key":"3_CR16","unstructured":"R. Greenlaw: Polynomial Completeness and Parallel Computation. Synthesis of Parallel Algorithms, Ed. J. Reif, Morgan-Kaufmann, 1993."},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"J. Gil, Y. Matias, U. Vishkin: Towards a theory of nearly constant time parallel algorithms. 32th Annual IEEE-FOCS, 698\u2013710, 1991.","DOI":"10.1109\/SFCS.1991.185438"},{"key":"3_CR18","unstructured":"J. J\u00e1J\u00e1: Parallel Algorithms. Addison-Wesley, 1992."},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0166-218X(91)90086-C","volume":"34","author":"R. Karp","year":"1991","unstructured":"R. Karp: An introduction to randomized algorithms. Discr Appl Math, 34, 165\u2013201, 1991.","journal-title":"Discr Appl Math"},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R.M. Karp","year":"1985","unstructured":"R.M. Karp, A. Wigderson: A fast parallel algorithm for the maximal independent set problem. J. of ACM, 32, 762\u2013773, 1985.","journal-title":"J. of ACM"},{"issue":"1","key":"3_CR21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R.M. Karp","year":"1986","unstructured":"R.M. Karp, E. Upfal, A. Wigderson: Constructing a Maximum Matching is in Random NC. Combinatorica 6(1), 35\u201348, 1986. A preliminary version also appeared in 17th Annual ACM-STOC, 1985.","journal-title":"Combinatorica"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"R. Karp and V. Ramachandran: Parallel Algorithms for Shared-Memory Machines. Handbook of T.C.S., Ed. J. van Leeuwen, Elsevier Science, Vol. A, Chapter 17, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"P.N. Klein, S. Sairam: A Parallel Randomized Approximation Scheme for Shortest Paths. 24th Annual ACM-STOC, 750\u2013758, 1992.","DOI":"10.1145\/129712.129785"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"P.N. Klein, S. Sairam: A linear-processor polylog-time algorithm for shortest paths in planar graphs. Proc. of the 34th Annual IEEE FOCS 259\u2013270, 1994.","DOI":"10.1109\/SFCS.1993.366861"},{"key":"3_CR25","first-page":"462","volume":"841","author":"D. Kavvadias","year":"1994","unstructured":"D. Kavvadias, G.E. Pantziou, P.G. Spirakis, C. D. Zaroliagis: Hammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths and Other Problems. 19th MFCS, LNCS, 841, 462\u2013472, 1994.","journal-title":"19th MFCS, LNCS"},{"key":"3_CR26","first-page":"447","volume":"56","author":"L. Ku\u010dera","year":"1984","unstructured":"L. Ku\u010dera: Expected behaviour of graph coloring algorithms. Fundamentals in Computation Theory, LNCS, 56, 447\u2013451, 1984.","journal-title":"LNCS"},{"key":"3_CR27","volume-title":"Fundamentals of Computing Theory","author":"L. Lovasz","year":"1979","unstructured":"L. Lovasz: On Determinants, Matchings and Random Algorithm. Fundamentals of Computing Theory, ed. L. Budach, Akademia-Verlag, Berlin, 1979."},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby: A simple parallel algorithm for the maximal independent set problem. SIAM J. on Computing, 15, 1036\u20131053, 1986. (also in 17th Annual ACM-STOC).","journal-title":"SIAM J. on Computing"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"S. Micali V.V. Vazirani: An O(\u221a\u00a6V\u2225E\u00a6) algorithm for finding maximum matching in general graphs. the 21st Annual Symp. on IEEE-FOCS. 17\u201327, 1980.","DOI":"10.1109\/SFCS.1980.12"},{"key":"3_CR30","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"K. Mulmuley, U.V. Vazirani, V.V Vazirani: Matching is as easy as matrix inversion. Combinatorica 7, 105\u2013113, 1987 (also in 19th Annual ACM-STOC, 345\u2013354, 1987.","journal-title":"Combinatorica"},{"key":"3_CR31","doi-asserted-by":"crossref","unstructured":"S. Nikoletseas, K. Palem, P. Spirakis, M. Yung: Short Vertex Disjoint paths and Multiconnectivity in Random Graphs: Reliable Networks Computing. 21st ICALP, LNCS, 508\u2013519, 1994.","DOI":"10.1007\/3-540-58201-0_94"},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"V. Pan: Fast and Efficient Algorithms for the Exact Inversion of Integer Matrices. Fifth Annual Foundations of Software Technology and Theoretical Computer Science Conference, pp. 504\u2013521, 1985.","DOI":"10.1007\/3-540-16042-6_29"},{"key":"3_CR33","volume-title":"CTI TR-90.10.25","author":"G. Pantziou","year":"1990","unstructured":"G. Pantziou, P. Spirakis and C. Zaroliagis: Coloring Random Graphs Efficiently in Parallel, through Adaptive Techniques. CTI TR-90.10.25, Comp. Techn. Institute, Patras. Also presented in the ALCOM Workshop on Graphs Algorithms, Data Structures and Computational Geometry, Berlin, October, 1990."},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"P. Raghavan, Motwani: Randomized Algorithms. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"P. Raghavan, C.D. Thompson: Provably good routing in graphs: regular arrays. 17th Annual ACM-STOC, 79\u201387, 1985.","DOI":"10.1145\/22145.22154"},{"key":"3_CR36","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1137\/0207020","volume":"7","author":"E. Reghbati","year":"1978","unstructured":"E. Reghbati, D. Corniel: Parallel computations in graph theory. SIAM J. on Computing 7, 230\u2013237, 1978.","journal-title":"SIAM J. on Computing"},{"key":"3_CR37","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"J. H. Reif","year":"1985","unstructured":"J. H. Reif: depth first search is inherently sequential. IPL 20, 229\u2013234, 1985.","journal-title":"IPL"},{"issue":"4","key":"3_CR38","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"J.T. Schwartz: Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. of ACM 27(4), 701\u2013717, 1980.","journal-title":"J. of ACM"},{"key":"3_CR39","first-page":"118","volume":"480","author":"M. Serna","year":"1991","unstructured":"M. Serna, P.G. Spirakis: Tight RNC Approximations to Max Flow. 8th Annual STACS, LNCS 480, 118\u2013126, 1991.","journal-title":"LNCS"},{"issue":"3","key":"3_CR40","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1137\/0215058","volume":"15","author":"J. R. Smith","year":"1986","unstructured":"J. R. Smith: Parallel algorithms for depth first searches I: planar graphs. SIAM J. on Computing 15(3), 814\u2013830, 1986.","journal-title":"SIAM J. on Computing"},{"key":"3_CR41","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"W.T. Tutte","year":"1947","unstructured":"W.T. Tutte: The Factorization of Linear Graphs. J. London Math. Soc. 22, pp. 107\u2013111, 1947.","journal-title":"J. London Math. Soc."},{"key":"3_CR42","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1137\/0220006","volume":"20","author":"J. Ullmann","year":"1991","unstructured":"J. Ullmann, M. Yannakakis: High Probability parallel transitive closure algorithms. SIAM J. of Computing 20, 100\u2013125, 1991.","journal-title":"SIAM J. of Computing"},{"key":"3_CR43","unstructured":"E. Urland: Experimental tests of efficient shortest paths heuristics for random graphs on the CM-2. Techn. Rep. 71, University of Geneva, August, 1994."},{"key":"3_CR44","doi-asserted-by":"crossref","unstructured":"J. Van Leeuwen: Graph Algorithms, in Handbook of T.C.S. Ed. J. van Leeuwen, Elsevier Science, Vol. A, 10, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50015-1"},{"key":"3_CR45","doi-asserted-by":"crossref","unstructured":"J.S. Vitter, P. Flajolet: Average-Case Analysis of Algorithms and Data Structures, in Handbook of T.C.S. Ed. J. van Leeuwen, Elsevier Science, Vol. A, 9, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50014-X"}],"container-title":["Lecture Notes in Computer Science","Solving Combinatorial Optimization Problems in Parallel"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0027117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T19:15:20Z","timestamp":1736104520000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0027117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540610434","9783540498759"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/bfb0027117","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}