{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T13:52:42Z","timestamp":1773150762297,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540095101","type":"print"},{"value":"9783540351689","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1979]]},"DOI":"10.1007\/3-540-09510-1_27","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:42:53Z","timestamp":1330188173000},"page":"338-339","source":"Crossref","is-referenced-by-count":2,"title":["Recent advances in the probabilistic analysis of graph-theoretic algorithms"],"prefix":"10.1007","author":[{"given":"Richard M.","family":"Karp","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D. and L.G. Valiant, Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings. Proc. Ninth ACM Symposium on Theory of Computing (1977)","DOI":"10.1145\/800105.803393"},{"key":"27_CR2","series-title":"Informatica Rapport IR 27","volume-title":"The Expected Number of Phases of the Dinic-Karzanov Network Flow Algorithm","author":"P. Apers","year":"1978","unstructured":"Apers, P., The Expected Number of Phases of the Dinic-Karzanov Network Flow Algorithm. Informatica Rapport IR 27. Vrije Universiteit, Amsterdam (1978)"},{"key":"27_CR3","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1137\/0206046","volume":"6","author":"V. Chv\u00e1tal","year":"1977","unstructured":"Chv\u00e1tal, V., Determining the Stability Number of a Graph. SIAM J. Comp 6 (1977) 643\u2013662.","journal-title":"SIAM J. Comp"},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P. and A. R\u00e9nyi., On Random Graphs I, Publicationes Mathematicae 6 (1959) 290\u2013297.","journal-title":"Publicationes Mathematicae"},{"key":"27_CR5","first-page":"17","volume":"5A","author":"P. Erd\u00f6s","year":"1960","unstructured":"Erd\u00f6s, P. and A. R\u00e9nyi, On the Evolution of Random Graphs, Publ. Math. Inst. Hung. Acad. Sci. 5A (1960), 17\u201361.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"27_CR6","first-page":"455","volume":"8A","author":"P. Erd\u00f6s","year":"1963","unstructured":"Erd\u00f6s, P. and A. R\u00e9nyi, On Random Matrices, Publ. Math. Inst. Hung. Acad. Sci., 8A (1963), 455\u2013461.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"27_CR7","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01894879","volume":"17","author":"P. Erd\u00f6s","year":"1966","unstructured":"Erd\u00f6s, P. and A. R\u00e9nyi, On the Existence of a Factor of Degree One of a Connected Random Graph, Acta Math. Acad. Sci. Hung. 17 (1966), 359\u2013368.","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"27_CR8","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"G. R. Grimmett","year":"1975","unstructured":"Grimmett, G. R. and C. J. H. McDiarmid, On Coloring Random Graphs, Math. Proc. Camb. Phil. Soc. 77 (1975), 313\u2013324.","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"27_CR9","unstructured":"Hamacher, H., Numerical Investigations on the Maximal Flow Algorithm of Karzanov. Report 78-7, Mathematisches Institut, Universit\u00e4t zu K\u00f6ln, (1978)"},{"key":"27_CR10","unstructured":"Karp, R. M., The Probabilistic Analysis of Some Combinatorial Search Algorithms. Algorithms and Complexity: New Directions and Recent Results (Ed. J. Traub), Academic Press (1976)."},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Karp, R. M., A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem. To appear in SIAM J. Comp. (1979).","DOI":"10.1137\/0208045"},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"Karp, R. M. Probabilistic Analysis of a Canonical Numbering Algorithm for Graphs. Proc. AMS Symposia in Applied Mathematics 34 (1979).","DOI":"10.1090\/pspum\/034\/525336"},{"key":"27_CR13","volume-title":"An Algorithm to Solve the m x n Assignment Problem in Expected Time O (mn log n), Memorandum No. UCB\/ERL M78\/67","author":"R. M. Karp","year":"1978","unstructured":"Karp, R. M., An Algorithm to Solve the m x n Assignment Problem in Expected Time O (mn log n), Memorandum No. UCB\/ERL M78\/67, Electronics Research Laboratory, University of California, Berkeley (1978)"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"Lueker, G. S., Maximization Problems on Graphs with Edge Weights Chosen From a Normal Distribution. Proc. Tenth ACM Symposium on Theory of Computing (1978)","DOI":"10.1145\/800133.804327"},{"key":"27_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0208001","volume":"8","author":"C. McDiarmid","year":"1979","unstructured":"McDiarmid, C., Determining the Chromatic Number of a Graph, SIAM J. Comp. 8 (1979) 1\u201314.","journal-title":"SIAM J. Comp."},{"key":"27_CR16","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0012-365X(76)90068-6","volume":"14","author":"L. Posa","year":"1976","unstructured":"Posa, L., Hamiltonian Circuits in Random Graphs, Discrete Math. 14 (1976) 359\u2013364.","journal-title":"Discrete Math."},{"key":"27_CR17","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1137\/0207011","volume":"7","author":"C. P. Schnorr","year":"1978","unstructured":"Schnorr, C. P., An Algorithm for Transitive Closure with Linear Expected Time. SIAM J. Comp. 7 (1978) 127\u2013133.","journal-title":"SIAM J. Comp."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-09510-1_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T17:34:29Z","timestamp":1687282469000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-09510-1_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1979]]},"ISBN":["9783540095101","9783540351689"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-09510-1_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1979]]}}}