{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:47:33Z","timestamp":1725551253063},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633976"},{"type":"electronic","value":"9783540695363"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63397-9_30","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T19:22:48Z","timestamp":1270495368000},"page":"388-401","source":"Crossref","is-referenced-by-count":2,"title":["Coloring in sublinear time"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Nolte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rainer","family":"Schrader","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N.; Kahale, N.: A spectral technique for coloring random 3-colorable graphs, Proceedings of the 26th Symposium on Theory of Computing, 1994","DOI":"10.1145\/195058.195187"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Angluin, D.; Valiant, L.G.: Fast probabilistic algorithms for Hamiltonian circuits and matchings, Journal of Computer System Science 18, 1979","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Blum, A.; Spencer, J.: Coloring Random and Semi-Random k-Colorable graphs, Journal of Algorithms 19, 1995","DOI":"10.1006\/jagm.1995.1034"},{"key":"30_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-49686-8","volume-title":"Markov chains with stationary transition probabilities","author":"K.L. Chung","year":"1960","unstructured":"Chung, K.L.: Markov chains with stationary transition probabilities, Springer Verlag, Heidelberg, 1960."},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Dyer, M.; Frieze, A.: The Solution of Some Random NP-Hard Problems in Polynomial Expected Time, Journal of Algorithms 10, 1989","DOI":"10.1016\/0196-6774(89)90001-1"},{"key":"30_CR6","volume-title":"An introduction to probability theory and its applications, Volume 1","author":"W. Feller","year":"1950","unstructured":"Feller, W.: An introduction to probability theory and its applications, Volume 1, John Wiley & Sons, New York, 1950"},{"key":"30_CR7","unstructured":"Garey, M.R.; Johnson, S.J.: Computers and Intractability, W.H. Freeman and Company, 1979"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"Jensen, T.; Toft, B.: Graph Coloring Problems, John Wiley & Sons, 1995","DOI":"10.1002\/9781118032497"},{"key":"30_CR9","unstructured":"Jerrum, J; Sorkin, G.: Simulated Annealing for Graph Bisection, Technical Report 1993, LFCS, University of Edinburgh"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Johnson, D.S.; Aragon, C.R.; McGeoch, L.A.; Schevon, C.: Optimization by Simulated Annealing: An Experimental Evaluation, Operations Research 39, 1991","DOI":"10.1287\/opre.39.3.378"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P.: Optimization by Simulated Annealing, Science 220, 1983.","DOI":"10.1126\/science.220.4598.671"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Kucera, L.: Expected behaviour of graph coloring algorithms, Lecture Notes in Computer Science 56, 1977","DOI":"10.1007\/3-540-08442-8_114"},{"key":"30_CR13","unstructured":"Laarhoven, P.J.M.; Aarts, E.H.L.: Simulated Annealing: Theory and Applications, Kluwer Academic Publishers, 1989."},{"key":"30_CR14","unstructured":"Lindvall, T.: Lectures on the Coupling method, John Wiley & Sons, 1992"},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"Metropolis, N.; Rosenbluth, M.; Rosenbluth, M.; Teller, A.; Teller, E.: Equation of state calculations by fast computer machines, Journal of Chemical Physics 21, 1953","DOI":"10.2172\/4390578"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Petford, A.D.; Welsh, D.J.A.: A Randomized 3-Coloring Algorithm, Discrete Mathematics 74 (1989), North Holland","DOI":"10.1016\/0012-365X(89)90214-8"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Sasaki, G.H.; Hajek, B.: The Time Complexity of Maximum Matching by Simulated Annealing, Journal of the Association for Computing Machinery 35, 1988","DOI":"10.1145\/42282.46160"},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"Turner, J.: Almost All k-Colorable Graphs Are Easy to Color, Journal of Algorithms 9, 1988","DOI":"10.1016\/0196-6774(88)90005-3"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63397-9_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T00:17:45Z","timestamp":1559002665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63397-9_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633976","9783540695363"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-63397-9_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}