{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:46:41Z","timestamp":1773704801783,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540343752","type":"print"},{"value":"9783540343783","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11758471_29","type":"book-chapter","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T10:34:15Z","timestamp":1149244455000},"page":"296-307","source":"Crossref","is-referenced-by-count":11,"title":["Distributed Approximation Algorithms for Planar 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":"29_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network Decomposition and Locality in Distributed Computation. In: Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"29_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":"29_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":"29_CR4","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M.: Distributed algorithms for weighted problems in sparse graphs. To appear in Journal of Discrete Algorithms (in Press) (Available online September 7, 2005)"},{"issue":"1-3","key":"29_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 Mathematics\u00a0143(1-3), 62\u201371 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"29_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-540-30140-0_24","volume-title":"Algorithms \u2013 ESA 2004","author":"A. Czygrinow","year":"2004","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Szyma\u0144ska, E.: A fast distributed algorithm for approximating the maximum matching. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 252\u2013263. Springer, Heidelberg (2004)"},{"key":"29_CR7","unstructured":"Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. In: Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 717\u2013724 (2003)"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Elkin, M.: An Overview of Distributed Approximation. ACM SIGACT News Distributed Computing Column\u00a035(4) (Whole number 132), 40\u201357 (2004)","DOI":"10.1145\/1054916.1054931"},{"issue":"1-3","key":"29_CR9","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0012-365X(94)00313-8","volume":"149","author":"S. Hakimi","year":"1996","unstructured":"Hakimi, S., Mitchem, J., Schmeichel, E.: Star arboricity of graphs. Discrete Mathematics\u00a0149(1-3), 93\u201398 (1996)","journal-title":"Discrete Mathematics"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"Ha\u0144\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: A faster distributed algorithm for computing maximal matching deterministically. In: Proceedings of PODC 1999, the Eighteen Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 219\u2013228 (1999)","DOI":"10.1145\/301308.301360"},{"key":"29_CR11","unstructured":"Jia, L., Rajaraman, R., Suel, R.: An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In: Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pp. 33\u201342 (2001)"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pp. 238\u2013251 (1995)","DOI":"10.1145\/224964.224990"},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: Constant-Time Distributed Dominating Set Approximation. In: 22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA (July 2003)","DOI":"10.1145\/872035.872040"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What Cannot Be Computed Locally! In: Proceedings of 23rd ACM Symposium on the Principles of Distributed Computing (PODC), pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"issue":"1","key":"29_CR15","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 Journal on Computing\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"29_CR16","doi-asserted-by":"publisher","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.\u00a015(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"29_CR17","doi-asserted-by":"publisher","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. SIAM, Philadelphia (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11758471_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:04:25Z","timestamp":1619507065000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11758471_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343752","9783540343783"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11758471_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}