{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:13:50Z","timestamp":1725664430827},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540587156"},{"type":"electronic","value":"9783540490548"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58715-2_120","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:41:16Z","timestamp":1330256476000},"page":"137-148","source":"Crossref","is-referenced-by-count":1,"title":["Coloring semi-random graphs in polynomial expected time"],"prefix":"10.1007","author":[{"given":"C. R.","family":"Subramanian","sequence":"first","affiliation":[]},{"given":"C. E.","family":"Madhavan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"A. Blum, \u201cSome Tools for Approximate 3-Coloring\u201d, Proceedings of FOCS, 1990, p. 554\u2013562.","DOI":"10.1109\/FSCS.1990.89576"},{"key":"12_CR2","unstructured":"A. Blum and J. Spencer, \u201cColoring Random and Semi-Random k-Colorable Graphs\u201d, Submitted to Journal of Algorithms."},{"key":"12_CR3","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","volume":"10","author":"M.E. Dyer","year":"1989","unstructured":"M.E. Dyer and A.M. Frieze, \u201cThe solution of Some Random NP-Hard Problems in Polynomial Expected Time\u201d, Journal of Algorithms, 10 (1989), p. 451\u2013489.","journal-title":"Journal of Algorithms"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"M.Furer and C.R. Subramanian, \u201cColoring Random Graphs\u201d, Proceedings of SWAT,1992.","DOI":"10.1007\/3-540-55706-7_24"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"M. Furer, C.R. Subramanian, and C.E. Veni Madhavan, \u201cColoring Random Graphs in Polynomial Expected Time\u201d, Proceedings of ISAAC, 1993.","DOI":"10.1007\/3-540-57568-5_232"},{"key":"12_CR6","unstructured":"D. Karger, R. Motwani, and M. Sudan, \u201cApproximate Graph Coloring by Semi-Definite Programming\u201d, Proceedings of FOCS, 1994."},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis, \u201cOn the Hardness of Approximating Minimization Problems\u201d, Proceedings of FOCS, 1992.","DOI":"10.1145\/167088.167172"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"C.R. Subramanian, \u201cImproved Algorithms for Coloring Random Graphs\u201d, Proceedings of ISAAC, 1994.","DOI":"10.1007\/3-540-58325-4_212"},{"key":"12_CR9","series-title":"Ph.D. thesis","volume-title":"Algorithms for Coloring Random and Semi-Random Graphs","author":"C.R. Subramanian","year":"1994","unstructured":"C.R. Subramanian, \u201cAlgorithms for Coloring Random and Semi-Random Graphs\u201d, Ph.D. thesis, Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India, October 1994."},{"key":"12_CR10","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0022-0000(86)90044-9","volume":"33","author":"M. Santha","year":"1986","unstructured":"M. Santha and U.V. Vazirani, \u201cGenerating quasi-random sequences from semirandom sources\u201d, Journal of Computer and System Sciences, 33 (1986), p.75\u201387.","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR11","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0196-6774(88)90005-3","volume":"9","author":"J.S. Turner","year":"1988","unstructured":"J.S. Turner, \u201cAlmost All k-colorable Graphs are Easy to Color\u201d, Journal of Algorithms, 9 (1988), p. 63\u201382.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Foundation of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58715-2_120.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:23:42Z","timestamp":1605630222000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58715-2_120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540587156","9783540490548"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-58715-2_120","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}