{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:06:17Z","timestamp":1758823577669,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_26","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"306-319","source":"Crossref","is-referenced-by-count":5,"title":["The Randomized Coloring Procedure with Symmetry-Breaking"],"prefix":"10.1007","author":[{"given":"Sriram","family":"Pemmaraju","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(96)00031-X","volume":"162","author":"B. Baker","year":"1996","unstructured":"Baker, B., Coffman, E.: Mutual exclusion scheduling. Theor. Comput. Sci.\u00a0162, 225\u2013243 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J. Beck","year":"1991","unstructured":"Beck, J.: An algorithmic approach to the Lov\u00e1sz Local Lemma. Random Structures and Algorithms\u00a02, 343\u2013365 (1991)","journal-title":"Random Structures and Algorithms"},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/978-3-662-04363-9","volume-title":"Scheduling computer and manufacturing processes","author":"J. Blazewicz","year":"2001","unstructured":"Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G., Weglarz, J.: Scheduling computer and manufacturing processes, 2nd edn., p. 485. Springer, Berlin (2001)","edition":"2"},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0095-8956(83)90017-5","volume":"34","author":"B. Bollob\u00e1s","year":"1983","unstructured":"Bollob\u00e1s, B., Guy, R.K.: Equitable and proportional coloring of trees. Journal of Combinatorial Theory, Series B\u00a034, 177\u2013186 (1983)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"H. Chernoff","year":"1963","unstructured":"Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. American Statistical Association Journal\u00a058, 13\u201330 (1963)","journal-title":"American Statistical Association Journal"},{"key":"26_CR6","series-title":"Colloq. Math. Soc. J. Bolyai","first-page":"609","volume-title":"Infinite and Finite","author":"P. Erd\u0151s","year":"1975","unstructured":"Erd\u0151s, P., Lov\u00e1sz, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In: Hajnal, A., et al. (eds.) Infinite and Finite. Colloq. Math. Soc. J. Bolyai, vol.\u00a011, pp. 609\u2013627. North Holland, Amsterdam (1975)"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1006\/jagm.2000.1097","volume":"37","author":"D.A. Grable","year":"2000","unstructured":"Grable, D.A., Panconesi, A.: Fast distributed algorithms for Brooks-Vizing colorings. Journal of Algorithms\u00a037, 85\u2013120 (2000)","journal-title":"Journal of Algorithms"},{"key":"26_CR8","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proc. IEEE Symposium on Foundations of Computer Science (2003)"},{"key":"26_CR9","first-page":"601","volume-title":"Combinatorial Theory and its Applications","author":"A. Hajnal","year":"1970","unstructured":"Hajnal, A., Szemer\u00e9di, E.: Proof of a conjecture of Erd\u00f6s. In: Erd\u00f6s, P., R\u00e9nyi, A., S\u00f3s, V.T. (eds.) Combinatorial Theory and its Applications, vol.\u00a0II, pp. 601\u2013603. North-Holland, Amsterdam (1970)"},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1137\/S0097539795294578","volume":"28","author":"H. Hind","year":"1998","unstructured":"Hind, H., Molloy, M., Reed, B.: Total colouring with $\\Delta + \\mbox{polylog}(\\Delta)$ colours. SIAM Journal on Computing\u00a028, 816\u2013821 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"26_CR11","unstructured":"Hou, Y.T., Kumar, V.S.A., Marathe, M.V., Srinivasan, A.: Personal communication (2006)"},{"key":"26_CR12","first-page":"85","volume-title":"Proceedings of the 7th Annual ACM-SIAM symposium on discrete algorithms, held in Atlanta, GA","author":"S. Irani","year":"1996","unstructured":"Irani, S., Leung, V.: Scheduling with conflicts, and applications to traffic signal control. In: Proceedings of the 7th Annual ACM-SIAM symposium on discrete algorithms, held in Atlanta, GA, pp. 85\u201394. SIAM, Philadelphia (1996)"},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1002\/rsa.10031","volume":"20","author":"S. Janson","year":"2002","unstructured":"Janson, S., Ruci\u0144ski, A.: The infamous upper tail. Random Structures and Algorithms\u00a020, 317\u2013342 (2002)","journal-title":"Random Structures and Algorithms"},{"key":"26_CR14","unstructured":"Johansson, A.: Asymptotic choice number for triangle free graphs. In DIMACS Technical Report, 91-5 (1996)"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0020-0190(99)00064-2","volume":"70","author":"\u00d6. Johansson","year":"1999","unstructured":"Johansson, \u00d6.: Simple distributed \u0394\u2009+\u20091-coloring of graphs. Information Processing Letters\u00a070, 229\u2013232 (1999)","journal-title":"Information Processing Letters"},{"key":"26_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jcta.1996.0001","volume":"73","author":"J. Kahn","year":"1996","unstructured":"Kahn, J.: Asymptotically good list-colorings. J.\u00a0Combinatorial Theory, Series A\u00a073, 1\u201359 (1996)","journal-title":"J.\u00a0Combinatorial Theory, Series A"},{"key":"26_CR17","unstructured":"Kierstead, H.A., Kostochka, A.V.: A Short Proof of the Hajnal-Szemeredi Theorem on Equitable Coloring. Combinatorics, Probability, and Computing (to appear)"},{"key":"26_CR18","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1017\/S0963548300001528","volume":"4","author":"J.H. Kim","year":"1995","unstructured":"Kim, J.H.: On Brooks\u2019 Theorem for Sparse Graphs. Combinatorics, Probability, and Computing\u00a04, 97\u2013132 (1995)","journal-title":"Combinatorics, Probability, and Computing"},{"issue":"1","key":"26_CR19","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/S0895480103436505","volume":"19","author":"A.V. Kostochka","year":"2005","unstructured":"Kostochka, A.V., Nakprasit, K., Pemmaraju, S.V.: On Equitable Coloring of d-Degenerate Graphs. SIAM J. Discret. Math.\u00a019(1), 83\u201395 (2005)","journal-title":"SIAM J. Discret. Math."},{"key":"26_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(82)80002-7","volume":"11","author":"J. Krarup","year":"1982","unstructured":"Krarup, J., de Werra, D.: Chromatic optimisation: Limitations, objectives, uses, references. Eur. J. Oper. Res.\u00a011, 1\u201319 (1982)","journal-title":"Eur. J. Oper. Res."},{"key":"26_CR21","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: Proc. ACM-SIAM Symposium on Discrete Algorithms (2004)"},{"issue":"2","key":"26_CR22","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/0022-0000(93)90033-S","volume":"47","author":"M. Luby","year":"1993","unstructured":"Luby, M.: Removing randomness in parallel computation without a processor penalty. Journal of Computer and System Sciences\u00a047(2), 250\u2013286 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR23","volume-title":"Graph Colouring and the Probabilistic Method","author":"M. Molloy","year":"2000","unstructured":"Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method. Springer, Heidelberg (2000)"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"Pemmaraju, S.V.: Equitable colorings extend Chernoff-Hoeffding bounds. In: Proceedings of the 5th International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX-RANDOM 2001), pp. 285\u2013296 (2001)","DOI":"10.1007\/3-540-44666-4_31"},{"key":"26_CR25","first-page":"224","volume-title":"Domain decomposition. Parallel multilevel methods for elliptic partial differential equations","author":"B.F. Smith","year":"1996","unstructured":"Smith, B.F., Bjorstad, P.E., Gropp, W.D.: Domain decomposition. Parallel multilevel methods for elliptic partial differential equations, p. 224. Cambridge University Press, Cambridge (1996)"},{"key":"26_CR26","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1137\/1015072","volume":"15","author":"A. Tucker","year":"1973","unstructured":"Tucker, A.: Perfect graphs and an application to optimizing municipal services. SIAM Review\u00a015, 585\u2013590 (1973)","journal-title":"SIAM Review"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T03:26:31Z","timestamp":1714620391000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}