{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:14Z","timestamp":1760202674744,"version":"3.40.4"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,12,18]],"date-time":"2013-12-18T00:00:00Z","timestamp":1387324800000},"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":[[2014,4]]},"DOI":"10.1007\/s00446-013-0203-2","type":"journal-article","created":{"date-parts":[[2013,12,17]],"date-time":"2013-12-17T19:21:43Z","timestamp":1387308103000},"page":"79-93","source":"Crossref","is-referenced-by-count":5,"title":["Combinatorial algorithms for distributed graph coloring"],"prefix":"10.1007","volume":"27","author":[{"given":"Leonid","family":"Barenboim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Elkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,12,18]]},"reference":[{"issue":"4","key":"203_CR1","doi-asserted-by":"crossref","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"203_CR2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01302963","volume":"14","author":"M Ajtai","year":"1994","unstructured":"Ajtai, M.: Recursive construction for 3-regular expanders. Combinatorica 14(4), 379\u2013416 (1994)","journal-title":"Combinatorica"},{"issue":"2","key":"203_CR3","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N Alon","year":"1986","unstructured":"Alon, N.: Eigen-values and expanders. Combinatorica 6(2), 83\u201396 (1986)","journal-title":"Combinatorica"},{"issue":"4","key":"203_CR4","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"},{"issue":"2","key":"203_CR5","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1006\/jcss.1997.1388","volume":"54","author":"N Alon","year":"1997","unstructured":"Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. J. Comput. Syst. Sci. 54(2), 255\u2013262 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"203_CR6","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.: Network decomposition and locality in distributed computation. In: Proceedings of the 30th IEEE Annual Symposium on Foundations of Computer, Science, pp. 364\u2013369, October 1989","key":"203_CR7","DOI":"10.1109\/SFCS.1989.63504"},{"doi-asserted-by":"crossref","unstructured":"Barenboim, L., Dolev, S., Ostrovsky, R.: Deterministic and energy-optimal wireless synchronization. In: Proceedings of the 25th International Symposium on Distributed Computing, pp. 237\u2013251 (2011)","key":"203_CR8","DOI":"10.1007\/978-3-642-24100-0_24"},{"doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. In: Proceedings of the 27th ACM Symposium on Principles of, Distributed Computing, pp. 25\u201334 (2008)","key":"203_CR9","DOI":"10.1145\/1400751.1400757"},{"unstructured":"Barenboim, L., Elkin, M.: Distributed $$({\\varDelta }+1)$$ ( \u0394 + 1 ) -coloring in linear (in $${\\varDelta }$$ \u0394 ) time. In: Proceedings of the 41th ACM Symposium on Theory of Computing, pp. 111\u2013120, 2009. See also http:\/\/arXiv.org\/abs\/0812.1379v2 (2008)","key":"203_CR10"},{"doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. In: Proceedings of the 29th ACM Symposium on Principles of, Distributed Computing, pp. 410\u2013419 (2010)","key":"203_CR11","DOI":"10.1145\/1835698.1835797"},{"issue":"7","key":"203_CR12","doi-asserted-by":"crossref","first-page":"2865","DOI":"10.1137\/080737174","volume":"39","author":"S Baswana","year":"2010","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM J. Comput. 39(7), 2865\u20132896 (2010)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Ben-Aroya, A., Ta-Shma, A.: A combinatorial construction of almost-Ramanujan graphs using the zig-zag product. In: Proceedings of the 40th ACM Symposium on Theory of, Computing, pp. 325\u2013334 (2008)","key":"203_CR13","DOI":"10.1145\/1374376.1374424"},{"issue":"5","key":"203_CR14","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1007\/s00493-006-0029-7","volume":"26","author":"Y Bilu","year":"2006","unstructured":"Bilu, Y., Linial, N.: Lifts, discrepancy and nearly optimal spectral gaps. Combinatorica 26(5), 495\u2013519 (2006)","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Bradonji\u0107, M., Kohler, E., Ostrovsky, R.: Near-optimal radio use for wireless network synchronization. In: Proceedings of the 5th International Workshop on Algorithmic Aspects of Wireless Sensor, Networks, pp. 15\u201328 (2009)","key":"203_CR15","DOI":"10.1007\/978-3-642-05434-1_4"},{"issue":"1","key":"203_CR16","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32\u201353 (1986)","journal-title":"Inf. Control"},{"doi-asserted-by":"crossref","unstructured":"Dinur, I.: The PCP theorem by gap amplification. In: Proceedings of the 38th ACM Symposium on Theory of, Computing, pp. 241\u2013250 (2006)","key":"203_CR17","DOI":"10.1145\/1132516.1132553"},{"issue":"4","key":"203_CR18","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1137\/S0097539705446962","volume":"36","author":"I Dinur","year":"2006","unstructured":"Dinur, I., Reingold, O.: Assignment testers: towards a combinatorial proof of the PCP theorem. SIAM J. Comput. 36(4), 975\u20131024 (2006)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"203_CR19","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All pairs almost shortest paths. SIAM J. Comput. 29(5), 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Elkin, M.: Computing almost shortest paths. In: Proceedings of the 20th ACM Symposium on Principles of, Distributed Computing, pp. 53\u201362 (2001)","key":"203_CR20","DOI":"10.1145\/383962.383983"},{"doi-asserted-by":"crossref","unstructured":"Elkin, M., Kortsarz, G.: Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. In: Proceedings of the 34th ACM Symposium on Theory of, Computing, pp. 438\u2013447 (2002)","key":"203_CR21","DOI":"10.1145\/509907.509972"},{"unstructured":"Elkin, M., Kortsarz, G.: Sublogarithmic approximation for telephone multicast: path out of jungle. In: Proceedings of the 14th ACM-Siam Symposium on Discrete Algorithms, pp. 76\u201385 (2003)","key":"203_CR22"},{"key":"203_CR23","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF02772959","volume":"51","author":"P Erd\u0151s","year":"1985","unstructured":"Erd\u0151s, P., Frankl, P., F\u00fcredi, Z.: Families of finite sets in which no set is covered by the union of $$r$$ r others. Israel J. Math. 51, 79\u201389 (1985)","journal-title":"Israel J. Math."},{"issue":"2","key":"203_CR24","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lovasz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"issue":"2","key":"203_CR25","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/inco.1997.2620","volume":"134","author":"Z Galil","year":"1997","unstructured":"Galil, Z., Margalit, O.: All pairs shortest distances for graphs with small integer length edges. Inf. Comput. 134(2), 103\u2013139 (1997)","journal-title":"Inf. Comput."},{"doi-asserted-by":"crossref","unstructured":"Garay, J.A., Kutten, S., Peleg, D.: A sub-linear timedistributed algorithm for minimum-weight spanning trees. In: Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer, Science, pp. 659\u2013668 (1993)","key":"203_CR26","DOI":"10.1109\/SFCS.1993.366821"},{"doi-asserted-by":"crossref","unstructured":"Goldberg, A., Plotkin, S.: Efficient parallel algorithms for $$({\\varDelta }+1)$$ ( \u0394 + 1 ) -coloring and maximal independent set problem. In: Proceedings 19th ACM Symposium on Theory of, Computing, pp. 315\u2013324 (1987)","key":"203_CR27","DOI":"10.1145\/28395.28429"},{"issue":"4","key":"203_CR28","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1137\/0401044","volume":"1","author":"A Goldberg","year":"1988","unstructured":"Goldberg, A., Plotkin, S., Shannon, G.: Parallel symmetry-breaking in sparse graphs. SIAM J. Discret. Math. 1(4), 434\u2013446 (1988)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"203_CR29","doi-asserted-by":"crossref","first-page":"1132","DOI":"10.1137\/S0097539797315744","volume":"29","author":"O Goldreich","year":"2000","unstructured":"Goldreich, O., Safra, S.: A combinatorial consistency lemma with application to proving the PCP theorem. SIAM J. Comput. 29(4), 1132\u20131154 (2000)","journal-title":"SIAM J. Comput."},{"unstructured":"Kale, S., Seshadhri, C.: Combinatorial approximation algorithms for MaxCut using random walks. In: Proceedings of the 2nd Symposium on Innovations in Computer, Science, pp. 367\u2013388 (2011)","key":"203_CR30"},{"doi-asserted-by":"crossref","unstructured":"Kothapalli, K., Scheideler, C., Onus, M., Schindelhauer, C.: Distributed coloring in $$O(\\sqrt{\\log n})$$ O ( log n ) bit rounds. In: 20th International Parallel and Distributed Processing Symposium (2006)","key":"203_CR31","DOI":"10.1109\/IPDPS.2006.1639281"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: Proceedings of the 21st ACM Symposium on Parallel Algorithms and Architectures, pp. 138\u2013144 (2009)","key":"203_CR32","DOI":"10.1145\/1583991.1584032"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd ACM Symposium on Principles of, Distributed Computing, pp. 300\u2013309 (2004)","key":"203_CR33","DOI":"10.1145\/1011767.1011811"},{"unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. http:\/\/arXiv.org\/abs\/1011.5470 (2010)","key":"203_CR34"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In Proc. of the 25th ACM Symp. on Principles of, Distributed Computing, pp. 7\u201315 (2006)","key":"203_CR35","DOI":"10.1145\/1146381.1146387"},{"doi-asserted-by":"crossref","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and application. In: Proceedings of the 14th ACM Symposium on Principles of, Distributed Computing, pp. 238\u2013249 (1995)","key":"203_CR36","DOI":"10.1145\/224964.224990"},{"issue":"1","key":"203_CR37","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."},{"key":"203_CR38","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A Lubotzky","year":"1988","unstructured":"Lubotzky, A., Philips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261\u2013277 (1988)","journal-title":"Combinatorica"},{"key":"203_CR39","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, 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"203_CR40","first-page":"51","volume":"24","author":"GA Margulis","year":"1988","unstructured":"Margulis, G.A.: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredaci Informatsii 24(1), 51\u201360 (1988)","journal-title":"Problemy Peredaci Informatsii"},{"doi-asserted-by":"crossref","unstructured":"Meir, O.: Combinatorial PCPs with efficient verifiers. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer, Science, pp. 463\u2013471 (2009)","key":"203_CR41","DOI":"10.1109\/FOCS.2009.10"},{"issue":"1","key":"203_CR42","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1006\/jctb.1994.1054","volume":"62","author":"M Morgenstern","year":"1994","unstructured":"Morgenstern, M.: Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q. J. Comb. Theory Ser. B 62(1), 44\u201362 (1994)","journal-title":"J. Comb. Theory Ser. B"},{"unstructured":"Oldham, J.: Combinatorial approximation algorithms for generalized flow problems. In: Proceedings of the 10th ACM-Siam Symposium on Discrete Algorithms, pp. 704\u2013714 (1999)","key":"203_CR43"},{"issue":"2","key":"203_CR44","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(2), 97\u2013100 (2001)","journal-title":"Distrib. Comput."},{"issue":"2","key":"203_CR45","first-page":"581","volume":"20","author":"A Panconesi","year":"1995","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 581\u2013592 (1995)","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach, chap. 8, pp. 91\u2013102. SIAM (2000)","key":"203_CR46","DOI":"10.1137\/1.9780898719772.ch8"},{"unstructured":"Pinsker, M.: On the complexity of a concentrator. In: Proceedings of the 7th International Teletrac Conference, pp. 318\/1\u2013318\/4 (1973)","key":"203_CR47"},{"doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected ST-connectivity in log-space. In: Proceedings of the 37th ACM Symposium on Theory of, Computing, pp. 376\u2013385 (2005)","key":"203_CR48","DOI":"10.1145\/1060590.1060647"},{"doi-asserted-by":"crossref","unstructured":"Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer, Science, pp. 3\u201313 (2000)","key":"203_CR49","DOI":"10.1109\/SFCS.2000.892006"},{"doi-asserted-by":"crossref","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem. In: Proceedings of the 24th ACM Symposium on Theory of, Computing, pp. 745\u2013749 (1995)","key":"203_CR50","DOI":"10.1145\/129712.129784"},{"doi-asserted-by":"crossref","unstructured":"Szegedy, M., Vishwanathan, S.: Locality based graph coloring. In: Proceedings 25th ACM Symposium on Theory of Computing, San Diego, CA, USA, pp. 201\u2013207, May 1993","key":"203_CR51","DOI":"10.1145\/167088.167156"},{"doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A new technique for distributed symmetry breaking. In: Proceedings of the 29th ACM Symposium on Principles of, Distributed Computing, pp. 257\u2013266 (2010)","key":"203_CR52","DOI":"10.1145\/1835698.1835760"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-013-0203-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-013-0203-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-013-0203-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T06:31:00Z","timestamp":1746081060000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-013-0203-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,18]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["203"],"URL":"https:\/\/doi.org\/10.1007\/s00446-013-0203-2","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2013,12,18]]}}}