{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:28:10Z","timestamp":1742912890647,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319301389"},{"type":"electronic","value":"9783319301396"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-30139-6_20","type":"book-chapter","created":{"date-parts":[[2016,2,19]],"date-time":"2016-02-19T08:35:02Z","timestamp":1455870902000},"page":"251-262","source":"Crossref","is-referenced-by-count":0,"title":["Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers"],"prefix":"10.1007","author":[{"given":"Toshihiro","family":"Fujito","sequence":"first","affiliation":[]},{"given":"Daichi","family":"Suzuki","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"7","key":"20_CR1","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1016\/j.tcs.2010.04.040","volume":"412","author":"A Armon","year":"2011","unstructured":"Armon, A.: On min-max \n                      \n                        \n                      \n                      $$r$$\n                      \n                        \n                          r\n                        \n                      \n                    -gatherings. Theor. Comput. Sci. 412(7), 573\u2013582 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-642-04355-0_21","volume-title":"Distributed Computing","author":"M \u00c5strand","year":"2009","unstructured":"\u00c5strand, M., Flor\u00e9en, P., Polishchuk, V., Rybicki, J., Suomela, J., Uitto, J.: A local 2-approximation algorithm for the vertex cover problem. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 191\u2013205. Springer, Heidelberg (2009)"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"\u00c5strand, M., Suomela, J.: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In: Proceedings of the Twenty-second Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2010, pp. 294\u2013302 (2010)","DOI":"10.1145\/1810479.1810533"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41, 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"20_CR5","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/j.tcs.2007.06.009","volume":"385","author":"A Berger","year":"2007","unstructured":"Berger, A., Fukunaga, T., Nagamochi, H., Parekh, O.: Approximability of the capacitated \n                      \n                        \n                      \n                      $$b$$\n                      \n                        \n                          b\n                        \n                      \n                    -edge dominating set problem. Theor. Comput. Sci. 385(1\u20133), 202\u2013213 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"20_CR6","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/s00453-007-9057-y","volume":"50","author":"A Berger","year":"2008","unstructured":"Berger, A., Parekh, O.: Linear time algorithms for generalized edge dominating set problems. Algorithmica 50(2), 244\u2013254 (2008)","journal-title":"Algorithmica"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-642-17493-3_6","volume-title":"Parameterized and Exact Computation","author":"D Binkele-Raible","year":"2010","unstructured":"Binkele-Raible, D., Fernau, H.: Enumerate and measure: improving parameter budget management. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 38\u201349. Springer, Heidelberg (2010)"},{"issue":"3","key":"20_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10878-006-7908-0","volume":"11","author":"M Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of edge dominating set problems. J. Comb. Optim. 11(3), 279\u2013290 (2006)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"20_CR9","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/s00224-014-9549-5","volume":"56","author":"B Escoffier","year":"2015","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T., Xiao, M.: New results on polynomial inapproximabilityand fixed parameter approximability of edge dominating set. Theor. Comput. Syst. 56(2), 330\u2013346 (2015)","journal-title":"Theor. Comput. Syst."},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/11847250_13","volume-title":"Parameterized and Exact Computation","author":"H Fernau","year":"2006","unstructured":"Fernau, H.: edge dominating set: Efficient enumeration-based exact algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 142\u2013153. Springer, Heidelberg (2006)"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-14031-0_6","volume-title":"Computing and Combinatorics","author":"H Fernau","year":"2010","unstructured":"Fernau, H., Fomin, F.V., Philip, G., Saurabh, S.: The curse of connectivity: t-total vertex (edge) cover. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol. 6196, pp. 34\u201343. Springer, Heidelberg (2010)"},{"issue":"2","key":"20_CR12","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.jda.2008.09.007","volume":"7","author":"H Fernau","year":"2009","unstructured":"Fernau, H., Manlove, D.F.: Vertex and edge covers with clustering properties: complexity and algorithms. J. Discrete Algorithms 7(2), 149\u2013167 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"20_CR13","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"20_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-319-08404-6_18","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"T Fujito","year":"2014","unstructured":"Fujito, T.: On matchings and b-edge dominating sets: a 2-approximation algorithm for the 3-Edge dominating set problem. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 206\u2013216. Springer, Heidelberg (2014)"},{"issue":"5","key":"20_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2528405","volume":"60","author":"M G\u00f6\u00f6s","year":"2013","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. J. ACM. 60(5), 1\u201323 (2013)","journal-title":"J. ACM."},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Ha\u0144\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 219\u2013225 (1998)","DOI":"10.7146\/brics.v4i38.18964"},{"issue":"3","key":"20_CR17","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/0406030","volume":"6","author":"JD Horton","year":"1993","unstructured":"Horton, J.D., Kilakos, K.: Minimum edge dominating sets. SIAM J. Discrete Math. 6(3), 375\u2013387 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"20_CR18","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1007\/BFb0049428","volume-title":"Algorithms \u2014 ESA '94","author":"H. B. Hunt","year":"1994","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: A unified approach to approximation schemes for NP- and PSPACE-hard problems for geometric graphs. In: Proceedings 2nd Annual European Symposium on Algorithms, pp. 424\u2013435 (1994)"},{"issue":"1","key":"20_CR19","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."},{"key":"20_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/11424758_68","volume-title":"Computational Science and Its Applications \u2013 ICCSA 2005","author":"M Ma\u0142afiejski","year":"2005","unstructured":"Ma\u0142afiejski, M., \u017byli\u0144ski, P.: Weakly cooperative guards in grids. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Lagan\u00e1, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol. 3480, pp. 647\u2013656. Springer, Heidelberg (2005)"},{"key":"20_CR21","unstructured":"Mitchell, S., Hedetniemi, S.: Edge domination in trees. In: Proceedings 8th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 489\u2013509 (1977)"},{"issue":"12","key":"20_CR22","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1016\/j.ipl.2009.02.017","volume":"109","author":"V Polishchuk","year":"2009","unstructured":"Polishchuk, V., Suomela, J.: A simple local 3-approximation algorithm for vertex cover. Inform. Process. Lett. 109(12), 642\u2013645 (2009)","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"20_CR23","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2011.10.001","volume":"414","author":"R Schmied","year":"2012","unstructured":"Schmied, R., Viehmann, C.: Approximating edge dominating set in dense graphs. Theor. Comput. Sci. 414(1), 92\u201399 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR24","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0020-0190(95)94093-8","volume":"56","author":"A Srinivasan","year":"1995","unstructured":"Srinivasan, A., Madhukar, K., Nagavamsi, P., Pandu, C., Pandu Rangan, C., Chang, M.S.: Edge domination on bipartite permutation graphs and cotriangulated graphs. Inform. Process. Lett. 56, 165\u2013171 (1995)","journal-title":"Inform. Process. Lett."},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Suomela, J.: Distributed algorithms for edge dominating sets. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010, pp. 365\u2013374 (2010)","DOI":"10.1145\/1835698.1835783"},{"issue":"2","key":"20_CR26","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\u201340 (2013)","journal-title":"ACM Comput. Surv."},{"key":"20_CR27","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.tcs.2012.06.022","volume":"511","author":"M Xiao","year":"2013","unstructured":"Xiao, M., Kloks, T., Poon, S.-H.: New parameterized algorithms for the edge dominating set problem. Theor. Comput. Sci. 511, 147\u2013158 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"20_CR28","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-30139-6_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T11:01:15Z","timestamp":1559386875000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-30139-6_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319301389","9783319301396"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-30139-6_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}