{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T02:00:15Z","timestamp":1725847215179},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319286839"},{"type":"electronic","value":"9783319286846"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-28684-6_10","type":"book-chapter","created":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T10:32:03Z","timestamp":1452594723000},"page":"110-121","source":"Crossref","is-referenced-by-count":1,"title":["Constant-Time Local Computation Algorithms"],"prefix":"10.1007","author":[{"given":"Yishay","family":"Mansour","sequence":"first","affiliation":[]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[]},{"given":"Shai","family":"Vardi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,13]]},"reference":[{"key":"10_CR1","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"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1007\/978-3-662-44777-2_33","volume-title":"Algorithms - ESA 2014","author":"G Even","year":"2014","unstructured":"Even, G., Medina, M., Ron, D.: Deterministic stateless centralized local algorithms for bounded degree graphs. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 394\u2013405. Springer, Heidelberg (2014)"},{"issue":"1","key":"10_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"10_CR4","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. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10_CR5","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1137\/080714403","volume":"39","author":"Z Lotker","year":"2009","unstructured":"Lotker, Z., Patt-Shamir, B., Ros\u00e9n, A.: Distributed approximate matching. SIAM J. Comput. 39(2), 445\u2013460 (2009)","journal-title":"SIAM J. Comput."},{"key":"10_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/978-3-642-31594-7_55","volume-title":"Automata, Languages, and Programming","author":"Y Mansour","year":"2012","unstructured":"Mansour, Y., Rubinstein, A., Vardi, S., Xie, N.: Converting online algorithms to local computation algorithms. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 653\u2013664. Springer, Heidelberg (2012)"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-40328-6_19","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"Y Mansour","year":"2013","unstructured":"Mansour, Y., Vardi, S.: A local computation approximation scheme to maximum matching. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol. 8096, pp. 260\u2013273. Springer, Heidelberg (2013)"},{"issue":"1","key":"10_CR8","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. Discrete Math. 233(1), 3\u201336 (2001)","journal-title":"Discrete Math."},{"key":"10_CR9","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"},{"issue":"2","key":"10_CR10","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. Distrib. Comput. 14(2), 97\u2013100 (2001)","journal-title":"Distrib. Comput."},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Reingold, O., Vardi, S.: New techniques and tighter bounds for local computation algorithms (2015). Under submission","DOI":"10.1016\/j.jcss.2016.05.007"},{"key":"10_CR12","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":"10_CR13","doi-asserted-by":"publisher","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":"10_CR14","doi-asserted-by":"publisher","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":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/3-540-44929-9_7","volume-title":"Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics","author":"R Uehara","year":"2000","unstructured":"Uehara, R., Chen, Z.-Z.: Parallel approximation algorithms for maximum weighted matching in general graphs. In: Watanabe, O., Hagiya, M., Ito, T., Leeuwen, J., Mosses, P.D. (eds.) TCS 2000. LNCS, vol. 1872, pp. 84\u201398. Springer, Heidelberg (2000)"},{"key":"10_CR16","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-540-30186-8_24","volume-title":"Distributed Computing","author":"M Wattenhofer","year":"2004","unstructured":"Wattenhofer, M., Wattenhofer, R.: Distributed weighted matching. In: Guerraoui, R. (ed.) DISC 2004. LNCS, vol. 3274, pp. 335\u2013348. Springer, Heidelberg (2004)"},{"issue":"4","key":"10_CR18","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1137\/110828691","volume":"41","author":"Y Yoshida","year":"2012","unstructured":"Yoshida, Y., Yamamoto, M., Ito, H.: Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SIAM J. Comput. 41(4), 1074\u20131093 (2012)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-28684-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T12:28:31Z","timestamp":1654086511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-28684-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319286839","9783319286846"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-28684-6_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}