{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:38:58Z","timestamp":1782970738154,"version":"3.54.5"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2009,1,9]],"date-time":"2009-01-09T00:00:00Z","timestamp":1231459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2009,3]]},"DOI":"10.1007\/s00446-008-0076-y","type":"journal-article","created":{"date-parts":[[2009,1,8]],"date-time":"2009-01-08T10:18:40Z","timestamp":1231409920000},"page":"395-403","source":"Crossref","is-referenced-by-count":36,"title":["Distributed computing with advice: information sensitivity of graph coloring"],"prefix":"10.1007","volume":"21","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Ilcinkas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,1,9]]},"reference":[{"issue":"4","key":"76_CR1","doi-asserted-by":"crossref","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 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"76_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":"76_CR3","doi-asserted-by":"crossref","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\u2014towards tight results. SIAM J. Comput. 27(3), 804\u2013915 (1998)","journal-title":"SIAM J. Comput."},{"key":"76_CR4","doi-asserted-by":"crossref","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. In: 32nd Int. Colloquium on Automata, Languages and Programming (ICALP), LNCS 3580, pp. 335\u2013346 (2005)","DOI":"10.1007\/11523468_28"},{"key":"76_CR5","doi-asserted-by":"crossref","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling schemes for tree representation. In: 7th Int. Workshop on Distributed Computing (IWDC), LNCS 3741, pp. 13\u201324 (2005)","DOI":"10.1007\/11603771_2"},{"key":"76_CR6","doi-asserted-by":"crossref","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In: 18th ACM Symp. on Theory of Computing (STOC), pp. 206\u2013219 (1986)","DOI":"10.1145\/12130.12151"},{"issue":"2","key":"76_CR7","doi-asserted-by":"crossref","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. 57(2), 187\u2013199 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"76_CR8","doi-asserted-by":"crossref","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. Distrib. Comput. 16, 121\u2013163 (2003)","journal-title":"Distrib. Comput."},{"key":"76_CR9","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: a new measure of difficulty for communication tasks. In: 25th ACM Symp. on Principles of Distributed Computing (PODC), pp. 179\u2013187 (2006)","DOI":"10.1145\/1146381.1146410"},{"key":"76_CR10","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with an oracle. In: 31st Int. Symp. on Mathematical Foundations of Computer Science (MFCS), LNCS 4162, Springer, pp. 24\u201337 (2006)","DOI":"10.1007\/11821069_2"},{"key":"76_CR11","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. In: 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2007)","DOI":"10.1145\/1248377.1248402"},{"key":"76_CR12","doi-asserted-by":"crossref","unstructured":"Goldberg, A., Plotkin, S.: Efficient parallel algorithms for (\u0394 +\u00a01)-coloring and maximal independent set problems. In: 19th ACM Symp. on Theory of Computing (STOC), pp. 315\u2013324 (1987)","DOI":"10.1145\/28395.28429"},{"key":"76_CR13","doi-asserted-by":"crossref","unstructured":"Goldberg, A., Plotkin, S., Shannon, G.: Parallel symmetry-breaking in sparse graphs. In: 19th ACM Symp. on Theory of Computing (STOC), pp. 315\u2013324 (1987)","DOI":"10.1145\/28395.28429"},{"key":"76_CR14","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility Among Combinatorial Problems. In: Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"76_CR15","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) (2006)"},{"key":"76_CR16","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed Locally! In: 23th ACM Symp. on Principles of Distributed Computing, (PODC), pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"76_CR17","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: 25th ACM Symp. on Principles of Distributed Computing (PODC), pp. 7\u201315 (2006)","DOI":"10.1145\/1146381.1146387"},{"issue":"1","key":"76_CR18","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"76_CR19","doi-asserted-by":"crossref","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. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"76_CR20","doi-asserted-by":"crossref","unstructured":"Lynch, N.: A hundred impossibility proofs for distributed computing. In: 8th ACM Symp. on Principles of Distributed Computing (PODC), pp. 1\u201328 (1989)","DOI":"10.1145\/72981.72982"},{"key":"76_CR21","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: Coloring unstructured radio networks. In: 17th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 39\u201348 (2005)","DOI":"10.1145\/1073970.1073977"},{"issue":"3","key":"76_CR22","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0404036","volume":"4","author":"M. Naor","year":"1991","unstructured":"Naor M.: A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete Math. 4(3), 409\u2013412 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"76_CR23","doi-asserted-by":"crossref","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? In: 25th ACM Symposium on Theory of Computing (STOC), pp. 184\u2013193 (1993)","DOI":"10.1145\/167088.167149"},{"key":"76_CR24","doi-asserted-by":"crossref","unstructured":"Nisse, N., Soguet, D.: Graph searching with advice. In: 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO), June 2007","DOI":"10.1007\/978-3-540-72951-8_6"},{"key":"76_CR25","doi-asserted-by":"crossref","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. Distrib. Comput. 14, 97\u2013100 (2001)","journal-title":"Distrib. Comput."},{"key":"76_CR26","doi-asserted-by":"crossref","unstructured":"Panconesi, A., Srinivasan, A.: Improved distributed algorithms for coloring and network decomposition problems. In: 24th ACM Symp. on Theory of Computing (STOC), pp. 581\u2013592 (1992)","DOI":"10.1145\/129712.129769"},{"issue":"2","key":"76_CR27","doi-asserted-by":"crossref","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. J. Algorithms 20(2), 356\u2013374 (1996)","journal-title":"J. Algorithms"},{"key":"76_CR28","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM Monographs on Discrete Mathematics and applications. Philadelphia, PA (2000)","DOI":"10.1137\/1.9780898719772"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-008-0076-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-008-0076-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-008-0076-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T21:26:30Z","timestamp":1738877190000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-008-0076-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,9]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["76"],"URL":"https:\/\/doi.org\/10.1007\/s00446-008-0076-y","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,9]]}}}