{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T09:56:58Z","timestamp":1776333418793,"version":"3.51.2"},"reference-count":51,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[1991,11,1]],"date-time":"1991-11-01T00:00:00Z","timestamp":688953600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":7929,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1991,11]]},"DOI":"10.1016\/0166-218x(91)90086-c","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T03:43:01Z","timestamp":1027654981000},"page":"165-201","source":"Crossref","is-referenced-by-count":65,"title":["An introduction to randomized algorithms"],"prefix":"10.1016","volume":"34","author":[{"given":"Richard M.","family":"Karp","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0166-218X(91)90086-C_BIB1_1","first-page":"263","volume":"146","author":"Adelson\u2013Velski\u01d0","year":"1962","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10.1016\/0166-218X(91)90086-C_BIB1_2","first-page":"1259","volume":"3","author":"Adelson\u2013Velski\u01d0","year":"1962","journal-title":"Soviet Math."},{"key":"10.1016\/0166-218X(91)90086-C_BIB2","series-title":"Tech. Rep.","article-title":"Recognizing primes in random polynomial time","author":"Adleman","year":"1988"},{"key":"10.1016\/0166-218X(91)90086-C_BIB3","series-title":"Proceedings of the Nineteenth ACM Symposium on Theory of Computing (STOC)","first-page":"132","article-title":"Deterministic simulation in LOGSPACE","author":"Ajtai","year":"1987"},{"key":"10.1016\/0166-218X(91)90086-C_BIB4","series-title":"Proceedings of the Thirtieth Symposium on Foundations of Computer Science (FOCS)","first-page":"540","article-title":"Randomized search trees","author":"Aragon","year":"1989"},{"key":"10.1016\/0166-218X(91)90086-C_BIB5","series-title":"Proceedings of the Eighteenth ACM Symposium on Theory of Computing (STOC)","first-page":"442","article-title":"Computing the volume is difficult","author":"B\u00e1r\u00e1ny","year":"1986"},{"key":"10.1016\/0166-218X(91)90086-C_BIB6","doi-asserted-by":"crossref","first-page":"842","DOI":"10.1073\/pnas.43.9.842","article-title":"Two theorems in graph theory","volume":"43","author":"Berge","year":"1957","journal-title":"Proc. Nat. Acad. Sci."},{"key":"10.1016\/0166-218X(91)90086-C_BIB7","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","article-title":"Factoring polynomials over large finite fields","volume":"24","author":"Berlekamp","year":"1970","journal-title":"Math. Comp."},{"key":"10.1016\/0166-218X(91)90086-C_BIB8","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","article-title":"How to generate cryptographically strong sequences of pseudo-random bits","volume":"13","author":"Blum","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(91)90086-C_BIB9","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1145\/12130.12136","article-title":"How hard is it to marry at random? (On the approximation of the permanent)","author":"Broder","year":"1986","journal-title":"Proceedings of the Eighteenth ACM Symposium on Theory of Computing (STOC)"},{"key":"10.1016\/0166-218X(91)90086-C_BIB10","first-page":"590","article-title":"An optimal algorithm for intersecting line segments in the plane","author":"Chazelle","year":"1988","journal-title":"Proceedings of the Twenty-Ninth Symposium on Foundations of Computer Science (FOCS)"},{"key":"10.1016\/0166-218X(91)90086-C_BIB11","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","article-title":"New applications of random sampling in computational geometry","volume":"2","author":"Clarkson","year":"1987","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0166-218X(91)90086-C_BIB12","first-page":"452","article-title":"A Las Vegas algorithm for linear programming when the dimension is small","author":"Clarkson","year":"1988","journal-title":"Proceedings of the Twenty-Ninth Symposium on Foundations of Computer Science (FOCS)"},{"key":"10.1016\/0166-218X(91)90086-C_BIB13","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","article-title":"Applications of random sampling in computational geometry II","volume":"4","author":"Clarkson","year":"1989","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0166-218X(91)90086-C_BIB14","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF02187741","article-title":"A fast Las Vegas algorithm for triangulating a simple polygon","volume":"4","author":"Clarkson","year":"1989","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0166-218X(91)90086-C_BIB15","unstructured":"A. Cohen and S. Wigderson, Manuscript, Hebrew University (1989)."},{"key":"10.1016\/0166-218X(91)90086-C_BIB16","first-page":"412","article-title":"Polytopes, permanents and graphs with large factors","author":"Dagum","year":"1988","journal-title":"Proceedings of the Twenty-Ninth Symposium on Foundations of Computer Science (FOCS)"},{"key":"10.1016\/0166-218X(91)90086-C_BIB17","series-title":"Proceedings of the Twenty-First ACM Symposium on Theory of Computing (STOC)","first-page":"375","article-title":"A random polynomial time algorithm for approximating the volume of convex bodies","author":"Dyer","year":"1989"},{"key":"10.1016\/0166-218X(91)90086-C_BIB18","first-page":"449","article-title":"Paths, trees and flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"10.1016\/0166-218X(91)90086-C_BIB19","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","article-title":"Computational complexity of probabilistic Turing machines","volume":"6","author":"Gill","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(91)90086-C_BIB20","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","article-title":"The knowledge complexity of interactive proof systems","volume":"18","author":"Goldwasser","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(91)90086-C_BIB21","series-title":"Proceedings of the Twenty-First ACM Symposium on Theory of Computing (STOC)","first-page":"12","article-title":"Pseudorandom generation from one-way functions","author":"Impagliazzo","year":"1989"},{"key":"10.1016\/0166-218X(91)90086-C_BIB22","series-title":"Proceedings of the Thirtieth Symposium on Foundations of Computer Science (FOCS)","first-page":"248","article-title":"How to recycle random bits","author":"Impagliazzo","year":"1989"},{"key":"10.1016\/0166-218X(91)90086-C_BIB23","series-title":"Proceedings of the Eighteenth ACM Symposium on Theory of Computing (STOC)","first-page":"235","article-title":"Conductance and the rapid mixing property for Markov chains: The approximation of the permanent resolved","author":"Jerrum","year":"1986"},{"key":"10.1016\/0166-218X(91)90086-C_BIB24","doi-asserted-by":"crossref","unstructured":"N. Karmarkar, R. Karp, R. Lipton, L. Lov\u00e1sz and M. Luby, A Monte Carlo algorithm for estimating the permanent, SIAM J. Comput., to appear.","DOI":"10.1137\/0222021"},{"key":"10.1016\/0166-218X(91)90086-C_BIB25","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0885-064X(85)90021-4","article-title":"Monte Carlo algorithms for the planar multiterminal network reliability problem","volume":"1","author":"Karp","year":"1985","journal-title":"J. Complexity"},{"key":"10.1016\/0166-218X(91)90086-C_BIB26","article-title":"A time-randomness trade-off","author":"Karp","year":"1985","journal-title":"AMS Conference on Probabilistic Computational Complexity, Durham, NH"},{"key":"10.1016\/0166-218X(91)90086-C_BIB27","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","article-title":"Efficient randomized pattern-matching algorithms","volume":"31","author":"Karp","year":"1987","journal-title":"IBM J. Res. Develop."},{"key":"10.1016\/0166-218X(91)90086-C_BIB28","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","article-title":"Constructing a perfect matching in random NC","volume":"6","author":"Karp","year":"1986","journal-title":"Combinatorica"},{"key":"10.1016\/0166-218X(91)90086-C_BIB29","series-title":"Proceedings of the Twentieth ACM Symposium on Theory of Computing (STOC)","first-page":"290","article-title":"A randomized parallel branch-and-bound procedure","author":"Karp","year":"1988"},{"key":"10.1016\/0166-218X(91)90086-C_BIB30","series-title":"The Art of Computer Programming, Vol. 3: Sorting and Searching","first-page":"217","author":"Knuth","year":"1973"},{"key":"10.1016\/0166-218X(91)90086-C_BIB31","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","article-title":"A simple parallel algorithm for the maximal independent set problem","volume":"15","author":"Luby","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(91)90086-C_BIB32","series-title":"Proceedings of the Twenty-First Symposium on Foundations of Computer Science (FOCS)","first-page":"17","article-title":"An O(|V\u2016E|) algorithm for finding maximum matching in general graphs","author":"Micali","year":"1980"},{"key":"10.1016\/0166-218X(91)90086-C_BIB33","series-title":"Proceedings of the Twenty-Ninth Symposium on Foundations of Computer Science (FOCS)","first-page":"580","article-title":"A fast planar partition algorithm, I","author":"Mulmuley","year":"1988"},{"key":"10.1016\/0166-218X(91)90086-C_BIB34","series-title":"Proceedings ACM SIGGRAPH","first-page":"379","article-title":"An efficient algorithm for hidden surface removal","author":"Mulmuley","year":"1989"},{"key":"10.1016\/0166-218X(91)90086-C_BIB35","series-title":"Proceedings of the Fifth ACM Symposium on Computational Geometry","first-page":"33","article-title":"A fast planar partition algorithm, II","author":"Mulmuley","year":"1989"},{"key":"10.1016\/0166-218X(91)90086-C_BIB36","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","article-title":"Matching is as easy as matrix inversion","volume":"7","author":"Mulmuley","year":"1987","journal-title":"Combinatorica"},{"key":"10.1016\/0166-218X(91)90086-C_BIB37","series-title":"Algorithms and Complexity","article-title":"Probabilistic algorithms","author":"Rabin","year":"1976"},{"key":"10.1016\/0166-218X(91)90086-C_BIB38","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF00288965","article-title":"The choice coordination problem","volume":"17","author":"Rabin","year":"1982","journal-title":"Acta Inform."},{"key":"10.1016\/0166-218X(91)90086-C_BIB39","first-page":"26","article-title":"Combinatorial mathematics","volume":"14","author":"Ryser","year":"1963"},{"key":"10.1016\/0166-218X(91)90086-C_BIB40","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","article-title":"Fast probabilistic algorithms for verification of polynomial identities","volume":"27","author":"Schwartz","year":"1980","journal-title":"J. ACM"},{"key":"10.1016\/0166-218X(91)90086-C_BIB41","series-title":"Proceedings of the Sixth ACM Symposium on Computational Geometry","article-title":"Linear programming and convex hulls made easy","author":"Seidel","year":"1990"},{"key":"10.1016\/0166-218X(91)90086-C_BIB42","series-title":"Proceedings of the Twenty-Second ACM Symposium on the Theory of Computing (STOC)","first-page":"11","article-title":"IP = PSPACE","author":"Shamir","year":"1990"},{"key":"10.1016\/0166-218X(91)90086-C_BIB43","series-title":"Structure in Complexity Theory","first-page":"325","article-title":"Expanders, randomness or time vs. space","author":"Sipser","year":"1986"},{"key":"10.1016\/0166-218X(91)90086-C_BIB44","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","article-title":"Self-adjusting binary search trees","volume":"26","author":"Sleator","year":"1985","journal-title":"J. ACM"},{"key":"10.1016\/0166-218X(91)90086-C_BIB45","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","article-title":"A fast Monte\u2013Carlo test for primality","volume":"6","author":"Solovay","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(91)90086-C_BIB46","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","article-title":"The factorization of linear graphs","volume":"22","author":"Tutte","year":"1947","journal-title":"J. London Math. Soc."},{"key":"10.1016\/0166-218X(91)90086-C_BIB47","series-title":"A theory of alternating paths and blossoms for proving correctness of the OVE) general graph matching algorithm, #89-1035","author":"Vazirani","year":"1989"},{"key":"10.1016\/0166-218X(91)90086-C_BIB48","series-title":"Proceedings of the Twenty-Sixth Symposium on Foundations of Computer Science (FOCS)","first-page":"417","article-title":"Random polynomial time is equal to semi-random polynomial time","author":"Vazirani","year":"1985"},{"key":"10.1016\/0166-218X(91)90086-C_BIB49","series-title":"Proceedings of the Twenty-Third Symposium on Foundations of Computer Science (FOCS)","first-page":"80","article-title":"Theory and applications of trapdoor functions","author":"Yao","year":"1982"},{"key":"10.1016\/0166-218X(91)90086-C_BIB50","series-title":"Ph.D. Thesis","article-title":"Parallel algorithms for combinatorial search problems","author":"Zhang","year":"1989"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X9190086C?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X9190086C?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T06:21:59Z","timestamp":1555136519000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0166218X9190086C"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,11]]},"references-count":51,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1991,11]]}},"alternative-id":["0166218X9190086C"],"URL":"https:\/\/doi.org\/10.1016\/0166-218x(91)90086-c","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1991,11]]}}}