{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:46:29Z","timestamp":1773704789681,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642106309","type":"print"},{"value":"9783642106316","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10631-6_68","type":"book-chapter","created":{"date-parts":[[2009,12,4]],"date-time":"2009-12-04T02:03:43Z","timestamp":1259892223000},"page":"668-678","source":"Crossref","is-referenced-by-count":6,"title":["Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs"],"prefix":"10.1007","author":[{"given":"Andrzej","family":"Czygrinow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Ha\u0144\u0107kowiak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edyta","family":"Szyma\u0144ska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"68_CR1","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. In: PODC 2008, pp. 25\u201334 (2008)","DOI":"10.1145\/1400751.1400757"},{"key":"68_CR2","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, 32\u201353 (1986)","journal-title":"Information and Control"},{"key":"68_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/3-540-45071-8_26","volume-title":"Computing and Combinatorics","author":"A. Czygrinow","year":"2003","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M.: Distributed Algorithm for Better Approximation of the Maximum Matching. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol.\u00a02697, pp. 242\u2013251. Springer, Heidelberg (2003)"},{"key":"68_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/11864219_27","volume-title":"Distributed Computing","author":"A. Czygrinow","year":"2006","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M.: Distributed approximation algorithms in unit-disc graphs. In: Dolev, S. (ed.) DISC 2006. LNCS, vol.\u00a04167, pp. 385\u2013398. Springer, Heidelberg (2006)"},{"issue":"1-3","key":"68_CR5","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.dam.2003.10.004","volume":"143","author":"A. Czygrinow","year":"2004","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Szyma\u0144ska, E.: Distributed algorithm for approximating the maximum matching. Discrete Applied Math.\u00a0143(1-3), 62\u201371 (2004)","journal-title":"Discrete Applied Math."},{"key":"68_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/11758471_29","volume-title":"Algorithms and Complexity","author":"A. Czygrinow","year":"2006","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Szyma\u0144ska, E.: Distributed Approximation Algorithms for Planar Graphs. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol.\u00a03998, pp. 296\u2013307. Springer, Heidelberg (2006)"},{"key":"68_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-87779-0_6","volume-title":"Distributed Computing","author":"A. Czygrinow","year":"2008","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 78\u201392. Springer, Heidelberg (2008)"},{"key":"68_CR8","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"issue":"4-132","key":"68_CR9","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/1054916.1054931","volume":"35","author":"M. Elkin","year":"2004","unstructured":"Elkin, M.: An Overview of Distributed Approximation. ACM SIGACT News Distributed Computing Column\u00a035(4-132), 40\u201357 (2004)","journal-title":"ACM SIGACT News Distributed Computing Column"},{"issue":"1","key":"68_CR10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0895480100373121","volume":"15","author":"M. Ha\u0144\u0107kowiak","year":"2001","unstructured":"Ha\u0144\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. SIAM J. Discrete Math.\u00a015(1), 41\u201357 (2001)","journal-title":"SIAM J. Discrete Math."},{"key":"68_CR11","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"A. Hopcroft","year":"1973","unstructured":"Hopcroft, A., Karp, R.: An n 5\/2 algorithm for maximum matching in bipartite graphs. SIAM J. on Comp.\u00a02, 225\u2013231 (1973)","journal-title":"SIAM J. on Comp."},{"issue":"2","key":"68_CR12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A. Israeli","year":"1986","unstructured":"Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Info. Proc. Lett.\u00a022(2), 77\u201380 (1986)","journal-title":"Info. Proc. Lett."},{"key":"68_CR13","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What Cannot Be Computed Locally! In: Proc. PODC, pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"68_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/11561927_21","volume-title":"Distributed Computing","author":"F. Kuhn","year":"2005","unstructured":"Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol.\u00a03724, pp. 273\u2013287. Springer, Heidelberg (2005)"},{"key":"68_CR15","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Local Approximation Schemes for Ad Hoc and Sensor Networks. In: 3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 97\u2013103 (2005)","DOI":"10.1145\/1080810.1080827"},{"key":"68_CR16","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. SODA, pp. 980\u2013989 (2005)","DOI":"10.1145\/1109557.1109666"},{"key":"68_CR17","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Patt-Shamir, B., Pettie, S.: Improved distributed approximate matching. In: SPAA 2008, pp. 129\u2013136 (2008)","DOI":"10.1145\/1378533.1378558"},{"issue":"2","key":"68_CR18","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"},{"key":"68_CR19","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Algorithms, A Locality-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Algorithms, A Locality-Sensitive Approach. SIAM Press, Philadelphia (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10631-6_68.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:32:21Z","timestamp":1606167141000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10631-6_68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642106309","9783642106316"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10631-6_68","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}