{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:54Z","timestamp":1759638114263,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315848"},{"type":"electronic","value":"9783642315855"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31585-5_37","type":"book-chapter","created":{"date-parts":[[2012,6,23]],"date-time":"2012-06-23T11:56:29Z","timestamp":1340452589000},"page":"403-415","source":"Crossref","is-referenced-by-count":13,"title":["On the Locality of Some NP-Complete Problems"],"prefix":"10.1007","author":[{"given":"Leonid","family":"Barenboim","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.: Network decomposition and locality in distributed computation. In: Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 364\u2013369 (October 1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"37_CR2","unstructured":"Barenboim, L.: On the locality of some NP-complete problems (2012), http:\/\/arXiv.org\/abs\/1204.6675"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. In: Proc. 27th ACM Symp. on Principles of Distributed Computing, pp. 25\u201334 (2008)","DOI":"10.1145\/1400751.1400757"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Distributed (\u0394\u2009+\u20091)-coloring in linear (in \u0394) time. In: Proc. 41st ACM Symp. on Theory of Computing, pp. 111\u2013120 (2009)","DOI":"10.1145\/1536414.1536432"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. In: Proc. 29th ACM Symp. on Principles of Distributed Computing, pp. 410\u2013419 (2010)","DOI":"10.1145\/1835698.1835797"},{"issue":"1","key":"37_CR6","doi-asserted-by":"publisher","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. Information and Control\u00a070(1), 32\u201353 (1986)","journal-title":"Information and Control"},{"key":"37_CR7","doi-asserted-by":"crossref","unstructured":"Goldberg, A., Plotkin, S.: Efficient parallel algorithms for (\u0394\u2009+\u20091) -coloring and maximal independent set problem. In: Proc. 19th ACM Symp. on Theory of Computing, pp. 315\u2013324 (1987)","DOI":"10.1145\/28395.28429"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local Distributed Decision. In: Proc. 52nd IEEE Symp. on Foundations of Computer Science, pp. 708\u2013717 (2011)","DOI":"10.1109\/FOCS.2011.17"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: Proc. 21st ACM Symp. on Parallel Algorithms and Architectures, pp. 138\u2013144 (2009)","DOI":"10.1145\/1583991.1584032"},{"key":"37_CR10","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. 17th ACM-SIAM Symp. on Discrete Algorithms, pp. 980\u2013989 (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"37_CR11","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local Computation: Lower and Upper Bounds (2010), http:\/\/arXiv.org\/abs\/1011.5470"},{"key":"37_CR12","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: Constant-time distributed dominating set approximation. In: 22nd ACM Symp. Principles of Distributed Computing, pp. 25\u201332 (2003)","DOI":"10.1145\/872035.872040"},{"key":"#cr-split#-37_CR13.1","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Oswald, Y., Wattenhofer, R.: What Can Be Approximated Locally? Case Study: Dominating Sets in Planar Graphs. In: Proc. 20th ACM Symp. on Parallelism in Algorithms and Architectures, pp. 46-54 (2008)","DOI":"10.1145\/1378533.1378540"},{"key":"#cr-split#-37_CR13.2","unstructured":"See also TIK report number 331, ETH Zurich (2010)"},{"key":"37_CR14","doi-asserted-by":"crossref","unstructured":"Linial, N.: Distributive Graph Algorithms-Global Solutions from Local Data. In: Proc. 28th IEEE Symp. on Foundations of Computer Science, pp. 331\u2013335 (1987)","DOI":"10.1109\/SFCS.1987.20"},{"issue":"4","key":"37_CR15","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/BF01303516","volume":"13","author":"N. Linial","year":"1993","unstructured":"Linial, N., Saks, M.: Low diameter graph decompositions. Combinatorica\u00a013(4), 441\u2013454 (1993)","journal-title":"Combinatorica"},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? In: Proc. 25th ACM Symp. on Theory of Computing, pp. 184\u2013193 (1993)","DOI":"10.1145\/167088.167149"},{"issue":"2","key":"37_CR17","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(2), 97\u2013100 (2001)","journal-title":"Distributed Computing"},{"issue":"2","key":"37_CR18","first-page":"581","volume":"20","author":"A. Panconesi","year":"1995","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. Journal of Algorithms\u00a020(2), 581\u2013592 (1995)","journal-title":"Journal of Algorithms"},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A New Technique For Distributed Symmetry Breaking. In: 29th ACM Symp. Principles of Distributed Computing, pp. 257\u2013266 (2010)","DOI":"10.1145\/1835698.1835760"},{"key":"37_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-642-22212-2_22","volume-title":"Structural Information and Communication Complexity","author":"J. Schneider","year":"2011","unstructured":"Schneider, J., Wattenhofer, R.: Distributed Coloring Depending on the Chromatic Number or the Neighborhood Growth. In: Kosowski, A., Yamashita, M. (eds.) SIROCCO 2011. LNCS, vol.\u00a06796, pp. 246\u2013257. Springer, Heidelberg (2011)"},{"issue":"1","key":"37_CR21","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing\u00a03(1), 103\u2013128 (2007)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31585-5_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T13:49:57Z","timestamp":1743601797000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31585-5_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315848","9783642315855"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31585-5_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}