{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:00:43Z","timestamp":1787500843242,"version":"build-2736575974"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T00:00:00Z","timestamp":1497916800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1444\/14"],"award-info":[{"award-number":["1444\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00224-017-9788-3","type":"journal-article","created":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T01:28:34Z","timestamp":1497922114000},"page":"249-267","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Constant-Time Local Computation Algorithms"],"prefix":"10.1007","volume":"62","author":[{"given":"Yishay","family":"Mansour","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shai","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,6,20]]},"reference":[{"key":"9788_CR1","unstructured":"Aho, A.V., Hopcroft, J.E.: The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston (1974)"},{"key":"9788_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Rubinfeld, R., Vardi, S., Xie, N.: Space-efficient local computation algorithms. In: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1132\u20131139 (2012)","DOI":"10.1137\/1.9781611973099.89"},{"issue":"1","key":"9788_CR3","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."},{"key":"9788_CR4","doi-asserted-by":"crossref","unstructured":"Even, G., Medina, M., Ron, D.: Deterministic stateless centralized local algorithms for bounded degree graphs. In: 22th Annual European Symposium on Algorithms (ESA), pp. 394\u2013405 (2014)","DOI":"10.1007\/978-3-662-44777-2_33"},{"key":"9788_CR5","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Levi, R., Medina, M., Suomela, J.: Non-local probes do not help with many graph problems. In: 30th International Symposium, on Distributed Computing (DISC), pp. 201\u2013214 (2016)","DOI":"10.1007\/978-3-662-53426-7_15"},{"issue":"1","key":"9788_CR6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1997","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"9788_CR7","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 175\u2013184 (2012)","DOI":"10.1145\/2332432.2332465"},{"key":"9788_CR8","doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Local approximation of covering and packing problems. In: Encyclopedia of Algorithms (2008)","DOI":"10.1007\/978-0-387-30162-4_209"},{"key":"9788_CR9","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proceedings of the 17Th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 980\u2013989 (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"9788_CR10","doi-asserted-by":"crossref","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1) (1992)","DOI":"10.1137\/0221015"},{"key":"9788_CR11","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Patt-Shamir, B., Ros\u00e9n, A.: Distributed approximate matching. SIAM J. Comput. 39(2) (2009)","DOI":"10.1137\/080714403"},{"key":"9788_CR12","doi-asserted-by":"crossref","unstructured":"Mansour, Y., Rubinstein, A., Vardi, S., Xie, N.: Converting online algorithms to local computation algorithms. In: Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP), pp. 653\u2013664 (2012)","DOI":"10.1007\/978-3-642-31594-7_55"},{"key":"9788_CR13","doi-asserted-by":"crossref","unstructured":"Mansour, Y., Vardi, S.: A Local computation approximation scheme to maximum matching. In: APPROX-RANDOM, pp. 260\u2013273 (2013)","DOI":"10.1007\/978-3-642-40328-6_19"},{"issue":"6","key":"9788_CR14","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.J.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9788_CR15","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0012-365X(00)00224-7","volume":"233","author":"J Ne\u0161et\u0159il","year":"2001","unstructured":"Ne\u0161et\u0159il, J., Milkov\u00e1, E., Ne\u0161et\u0159ilov\u00e1, H.: Otakar Bor\u016fvka on minimum spanning tree problem: Translation of both the 1926 papers, comments, history. Discret. Math. 233(1), 3\u201336 (2001)","journal-title":"Discret. Math."},{"key":"9788_CR16","doi-asserted-by":"crossref","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 327\u2013336 (2008)","DOI":"10.1109\/FOCS.2008.81"},{"key":"9788_CR17","unstructured":"Oxley, J.: Matroid Theory. Oxford University Press (1992)"},{"issue":"2","key":"9788_CR18","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."},{"key":"9788_CR19","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-sensitive approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"issue":"7","key":"9788_CR20","doi-asserted-by":"crossref","first-page":"1180","DOI":"10.1016\/j.jcss.2016.05.007","volume":"82","author":"O Reingold","year":"2016","unstructured":"Reingold, O., Vardi, S.: New techniques and tighter bounds for local computation algorithms. J. Comput. Syst. Sci. 82(7), 1180\u20131200 (2016)","journal-title":"J. Comput. Syst. Sci."},{"key":"9788_CR21","unstructured":"Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS), pp. 223\u2013238 (2011)"},{"issue":"2","key":"9788_CR22","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/2431211.2431223","volume":"45","author":"J Suomela","year":"2013","unstructured":"Suomela, J.: Survey of local algorithms. ACM Comput. Surv. 45(2), 24 (2013)","journal-title":"ACM Comput. Surv."},{"key":"9788_CR23","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data structures and network algorithms","author":"RE Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data structures and network algorithms. Society for industrial and applied mathematics, Philadelphia (1983)"},{"key":"9788_CR24","doi-asserted-by":"crossref","unstructured":"Uehara, R., Chen, Z.: Parallel approximation algorithms for maximum weighted matching in general graphs. In: Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics, International Conference IFIP TCS, pp. 84\u201398 (2000)","DOI":"10.1007\/3-540-44929-9_7"},{"key":"9788_CR25","volume-title":"Designing Local Computation Algorithms and Mechanisms. PhD Thesis","author":"S Vardi","year":"2015","unstructured":"Vardi, S.: Designing Local Computation Algorithms and Mechanisms. PhD Thesis. Tel Aviv University, Tel Aviv (2015)"},{"key":"9788_CR26","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer (2001)"},{"key":"9788_CR27","doi-asserted-by":"crossref","unstructured":"Wattenhofer, M., Wattenhofer, R.: Distributed weighted matching. In: DISC, pp. 335\u2013348 (2004)","DOI":"10.1007\/978-3-540-30186-8_24"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9788-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9788-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9788-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T05:27:55Z","timestamp":1569475675000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9788-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,20]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["9788"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9788-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,20]]}}}