{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:45:28Z","timestamp":1725551128247},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540006237"},{"type":"electronic","value":"9783540364948"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_43","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T21:12:04Z","timestamp":1269897124000},"page":"487-498","source":"Crossref","is-referenced-by-count":7,"title":["Colouring Random Graphs in Expected Polynomial Time"],"prefix":"10.1007","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anusch","family":"Taraz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Molloy, M.: The analysis of a list-coloring algorithm on a random graph, Proc. 38th. IEEE Symp. Found. of Comp. Sci. (1997) 204\u2013212","DOI":"10.1109\/SFCS.1997.646109"},{"key":"43_CR2","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"L.L. Beck","year":"1983","unstructured":"Beck, L.L., Matula, D.W.: Smallest-last ordering and clustering and graph coloring algorithms, J. ACM 30 (1983) 417\u2013427","journal-title":"J. ACM"},{"key":"43_CR3","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time O(1.3446 n ): a no-MIS algorithm, Proc. 36th. IEEE Symp. Found. of Comp. Sci. (1995) 444\u2013453"},{"key":"43_CR4","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B.: Random graphs, 2nd edition, Cambridge University Press 2001","DOI":"10.1017\/CBO9780511814068"},{"key":"43_CR5","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A.: Finding sparse induced subgraphs of semirandom graphs. Proc. 6th. Int. Workshop Randomization and Approximation Techniques in Comp. Sci. (2002) 139\u2013148","DOI":"10.1007\/3-540-45726-7_12"},{"key":"43_CR6","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A.: Finding large independent sets in expected polynomial time. To appear in Proc. STACS 2003","DOI":"10.1007\/3-540-36494-3_45"},{"key":"43_CR7","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","volume":"10","author":"M. Dyer","year":"1989","unstructured":"Dyer, M., Frieze, A.: The solution of some NP-hard problems in polynomial expected time, J. Algorithms 10 (1989) 451\u2013489","journal-title":"J. Algorithms"},{"key":"43_CR8","unstructured":"Eppstein, D.: Small maximal independent sets and faster exact graph coloring. To appear in J. Graph Algorithms and Applications"},{"key":"43_CR9","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. Proc. 11. IEEE Conf. Comput. Complexity (1996) 278\u2013287"},{"key":"43_CR10","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1006\/jcss.2001.1773","volume":"63","author":"U. Feige","year":"2001","unstructured":"Feige, U., Kilian, J.: Heuristics for semirandom graph problems. J. Comput. and System Sci. 63 (2001) 639\u2013671","journal-title":"J. Comput. and System Sci."},{"key":"43_CR11","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF02579329","volume":"1","author":"Z. F\u00fcredi","year":"1981","unstructured":"F\u00fcredi, Z., Komlo\u015b, J.: The eigenvalues of random symmetric matrices, Combinatorica 1 (1981) 233\u2013241","journal-title":"Combinatorica"},{"key":"43_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/3-540-57568-5_232","volume-title":"Algorithms and Comput","author":"M. F\u00fcrer","year":"1993","unstructured":"F\u00fcrer, M., Subramanian, C.R., Veni Madhavan, C.E.: Coloring random graphs in polynomial expected time. Algorithms and Comput. (Hong Kong 1993), Springer LNCS 762, 31\u201337"},{"key":"43_CR13","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","volume":"10","author":"A. Frieze","year":"1997","unstructured":"Frieze, A., McDiarmid, C.: Algorithmic theory of random graphs. Random Structures and Algorithms 10 (1997) 5\u201342","journal-title":"Random Structures and Algorithms"},{"key":"43_CR14","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"G. Grimmett","year":"1975","unstructured":"Grimmett, G., McDiarmid, C.: On colouring random graphs. Math. Proc. Cam. Phil. Soc 77 (1975) 313\u2013324","journal-title":"Math. Proc. Cam. Phil. Soc"},{"key":"43_CR15","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Springer 1988","DOI":"10.1007\/978-3-642-97881-4"},{"key":"43_CR16","doi-asserted-by":"crossref","unstructured":"Janson, S., Luczak, T., Ruci\u0144ski, A.: Random Graphs. Wiley 2000","DOI":"10.1002\/9781118032718"},{"key":"43_CR17","first-page":"269","volume":"2","author":"F. Juh\u00e1sz","year":"1982","unstructured":"Juh\u00e1sz, F.: The asymptotic behaviour of Lov\u00e1sz. function for random graphs, Combinatorica 2 (1982) 269\u2013280","journal-title":"function for random graphs, Combinatorica"},{"key":"43_CR18","doi-asserted-by":"crossref","unstructured":"Karger, D., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. Proc. of the 35th. IEEE Symp. on Foundations of Computer Science (1994) 2\u201313","DOI":"10.1109\/SFCS.1994.365710"},{"key":"43_CR19","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Complexity of computer computations. Plenum Press (1972) 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"43_CR20","unstructured":"Karp, R.: The probabilistic analysis of combinatorial optimization algorithms. Proc. Int. Congress of Mathematicians (1984) 1601\u20131609."},{"key":"43_CR21","doi-asserted-by":"crossref","unstructured":"Knuth, D.: The sandwich theorem, Electron. J. Combin. 1 (1994)","DOI":"10.37236\/1193"},{"key":"43_CR22","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/A:1013899527204","volume":"6","author":"M. Krivelevich","year":"2002","unstructured":"Krivelevich, M., Vu, V.H.: Approximating the independence number and the chromatic number in expected polynomial time. J. of Combinatorial Optimization 6 (2002) 143\u2013155","journal-title":"J. of Combinatorial Optimization"},{"key":"43_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(01)00187-9","volume":"81","author":"M. Krivelevich","year":"2002","unstructured":"Krivelevich, M.: Deciding k-colorability in expected polynomial time, Information Processing Letters 81 (2002) 1\u20136","journal-title":"Information Processing Letters"},{"key":"43_CR24","doi-asserted-by":"crossref","unstructured":"Krivelevich, M.: Coloring random graphs-an algorithmic perspective, Proc. 2nd Coll. on Mathematics and Computer Science, B. Chauvin et al. Eds., Birkhauser, Basel (2002) 175\u2013195.","DOI":"10.1007\/978-3-0348-8211-8_11"},{"key":"43_CR25","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0020-0190(98)00092-1","volume":"67","author":"M. Krivelevich","year":"1998","unstructured":"Krivelevich, M., Sudakov, B.: Coloring random graphs. Informat. Proc. Letters 67 (1998) 71\u201374","journal-title":"Informat. Proc. Letters"},{"key":"43_CR26","first-page":"674","volume":"12","author":"L. Ku\u0109era","year":"1991","unstructured":"Ku\u0109era, L.: The greedy coloring is a bad probabilistic algorithm. J. Algorithms 12 (1991) 674\u2013684","journal-title":"The greedy coloring is a bad probabilistic algorithm. J. Algorithms"},{"key":"43_CR27","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E.L. Lawler","year":"1976","unstructured":"Lawler, E.L.: A note on the complexity of the chromatic number problem, Information Processing Letters 5 (1976) 66\u201367","journal-title":"Information Processing Letters"},{"key":"43_CR28","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1006\/jctb.1996.0036","volume":"67","author":"B. Pittel","year":"1996","unstructured":"Pittel, B., Spencer, J., Wormald, N.: Sudden emergence of a giant k-core in a random graph. JCTB 67 (1996) 111\u2013151","journal-title":"JCTB"},{"key":"43_CR29","first-page":"275","volume":"3","author":"H.J. Pr\u00f6mel","year":"1992","unstructured":"Pr\u00f6mel, H.J., Steger, A.: Coloring clique-free graphs in polynomial expected time, Random Str. Alg. 3 (1992) 275\u2013302","journal-title":"Random Str. Alg."}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T10:21:11Z","timestamp":1591179671000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_43","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}