{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:16Z","timestamp":1759638736979},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734192"},{"type":"electronic","value":"9783540734208"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_22","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"231-242","source":"Crossref","is-referenced-by-count":16,"title":["Distributed Computing with Advice: Information Sensitivity of Graph Coloring"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Ilcinkas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"22_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. Algorithms\u00a07(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A., Luby, M., Plotkin, S.: Network Decomposition and Locality in Distributed Computation. In: 30th Symp. on Foundations of Computer Science(FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"issue":"3","key":"22_CR3","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free Bits, PCPs, and Nonapproximability \u2013 Towards Tight Results. SIAM Journal on Computing\u00a027(3), 804\u2013915 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/11523468_28","volume-title":"Automata, Languages and Programming","author":"R. Cohen","year":"2005","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-Guided Graph Exploration by a Finite Automaton. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 335\u2013346. Springer, Heidelberg (2005)"},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/11603771_2","volume-title":"Distributed Computing \u2013 IWDC 2005","author":"R. Cohen","year":"2005","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling Schemes for Tree Representation. In: Pal, A., Kshemkalyani, A.D., Kumar, R., Gupta, A. (eds.) IWDC 2005. LNCS, vol.\u00a03741, pp. 13\u201324. Springer, Heidelberg (2005)"},{"key":"22_CR6","first-page":"206","volume-title":"STOC","author":"R. Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In: STOC. 18th ACM Symp. on Theory of Computing, pp. 206\u2013219. ACM Press, New York (1986)"},{"issue":"2","key":"22_CR7","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero Knowledge and the Chromatic Number. J. Comput. Syst. Sci.\u00a057(2), 187\u2013199 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s00446-003-0091-y","volume":"16","author":"F. Fich","year":"2003","unstructured":"Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distributed Computing\u00a016, 121\u2013163 (2003)","journal-title":"Distributed Computing"},{"key":"22_CR9","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/1146381.1146410","volume-title":"PODC","author":"P. Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: a new measure of difficulty for communication tasks. In: PODC. 25th ACM Symp. on Principles of Distributed Computing, pp. 179\u2013187. ACM Press, New York (2006)"},{"key":"22_CR10","first-page":"315","volume-title":"STOC","author":"A. Goldberg","year":"1987","unstructured":"Goldberg, A., Plotkin, S.: Efficient parallel algorithms for (\u0394\u2009+\u20091)-coloring and maximal independent set problems. In: STOC. 19th ACM Symp. on Theory of Computing, pp. 315\u2013324. ACM Press, New York (1987)"},{"key":"22_CR11","first-page":"315","volume-title":"STOC","author":"A. Goldberg","year":"1987","unstructured":"Goldberg, A., Plotkin, S., Shannon, G.: Parallel symmetry-breaking in sparse graphs. In: STOC. 19th ACM Symp. on Theory of Computing, pp. 315\u2013324. ACM Press, New York (1987)"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility Among Combinatorial Problems. Complexity of Computer Computations, 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"22_CR13","volume-title":"20th IEEE International Parallel and Distributed Processing Symposium (IPDPS)","author":"K. Kothapalli","year":"2006","unstructured":"Kothapalli, K., Onus, M., Scheideler, C., Schindelhauer, C.: Distributed coloring in $O(\\sqrt{\\log n})$ bit rounds. In: 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1145\/1011767.1011811","volume-title":"PODC","author":"F. Kuhn","year":"2004","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed Locally! In: PODC. 23th ACM Symp. on Principles of Distributed Computing, pp. 300\u2013309. ACM Press, New York (2004)"},{"key":"22_CR15","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/1146381.1146387","volume-title":"PODC","author":"F. Kuhn","year":"2006","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: PODC. 25th ACM Symp. on Principles of Distributed Computing, pp. 7\u201315. ACM Press, New York (2006)"},{"issue":"1","key":"22_CR16","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. on Computing\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM J. on Computing"},{"issue":"4","key":"22_CR17","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput.\u00a015(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"22_CR18","first-page":"1","volume-title":"PODC","author":"N. Lynch","year":"1989","unstructured":"Lynch, N.: A hundred impossibility proofs for distributed computing. In: PODC. 8th ACM Symp. on Principles of Distributed Computing, pp. 1\u201328. ACM Press, New York (1989)"},{"key":"22_CR19","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/1073970.1073977","volume-title":"SPAA","author":"T. Moscibroda","year":"2005","unstructured":"Moscibroda, T., Wattenhofer, R.: Coloring unstructured radio networks. In: SPAA. 17th ACM Symp. on Parallelism in Algorithms and Architectures, pp. 39\u201348. ACM Press, New York (2005)"},{"key":"22_CR20","first-page":"184","volume-title":"STOC","author":"M. Naor","year":"1993","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? In: STOC. 25th ACM Symposium on Theory of Computing, pp. 184\u2013193. ACM Press, New York (1993)"},{"key":"22_CR21","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/PL00008932","volume":"14","author":"A. Panconesi","year":"2001","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distributed Computing\u00a014, 97\u2013100 (2001)","journal-title":"Distributed Computing"},{"key":"22_CR22","first-page":"581","volume-title":"STOC","author":"A. Panconesi","year":"1992","unstructured":"Panconesi, A., Srinivasan, A.: Improved distributed algorithms for coloring and network decomposition problems. In: STOC. 24th ACM Symp. on Theory of Computing, pp. 581\u2013592. ACM Press, New York (1992)"},{"issue":"2","key":"22_CR23","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A. Panconesi","year":"1996","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. Journal of Algorithms\u00a020(2), 356\u2013374 (1996)","journal-title":"Journal of Algorithms"},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics (2000)","DOI":"10.1137\/1.9780898719772"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T22:39:27Z","timestamp":1684017567000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}