{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:44Z","timestamp":1740109424340,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,4,3]],"date-time":"2017-04-03T00:00:00Z","timestamp":1491177600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,4,3]],"date-time":"2017-04-03T00:00:00Z","timestamp":1491177600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["26330010"],"award-info":[{"award-number":["26330010"]}],"id":[{"id":"10.13039\/501100001691","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,4]]},"DOI":"10.1007\/s00224-017-9764-y","type":"journal-article","created":{"date-parts":[[2017,4,3]],"date-time":"2017-04-03T01:55:16Z","timestamp":1491184516000},"page":"533-556","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Approximating (Connected) 2-Edge Dominating Set by a Tree"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7892-6426","authenticated-orcid":false,"given":"Toshihiro","family":"Fujito","sequence":"first","affiliation":[]},{"given":"Tomoaki","family":"Shimoda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,4,3]]},"reference":[{"key":"9764_CR1","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s10479-006-0045-4","volume":"146","author":"J Alber","year":"2006","unstructured":"Alber, J., Betzler, N., Niedermeier, R.: Experiments on data reduction for optimal domination in networks. Ann. Oper. Res. 146, 105\u2013117 (2006)","journal-title":"Ann. Oper. Res."},{"key":"9764_CR2","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0020-0190(93)90072-H","volume":"47","author":"EM Arkin","year":"1993","unstructured":"Arkin, E. M., Halld\u00f3rsson, M. M., Hassin, R.: Approximating the tree and tour covers of a graph. Inform. Process. Lett. 47, 275\u2013282 (1993)","journal-title":"Inform. Process. Lett."},{"issue":"7","key":"9764_CR3","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 r-gatherings. Theor. Comput. Sci. 412(7), 573\u2013582 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9764_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":"9764_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 b-edge dominating set problem. Theory Comput Syst. 385(1\u20133), 202\u2013213 (2007)","journal-title":"Theory Comput Syst."},{"key":"9764_CR6","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-642-17493-3_6","volume-title":"Proceedings International Conference on Parameterized and Exact Computation","author":"D Binkele-Raible","year":"2010","unstructured":"Binkele-Raible, D, Fernau, H.: Enumerate and Measure: Improving Parameter Budget Management. In: Proceedings International Conference on Parameterized and Exact Computation, pp. 38\u201349. Springer, Heidelberg (2010)"},{"key":"9764_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-23830-1_8","volume-title":"Connected Dominating Set in Sensor Networks and MANETs","author":"J Blum","year":"2005","unstructured":"Blum, J., Ding, M., Thaeler, A., Cheng, X.: Connected Dominating Set in Sensor Networks and MANETs. Springer, New York (2005)"},{"key":"9764_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-011-1040-3","volume":"28","author":"M Chellali","year":"2012","unstructured":"Chellali, M., Favaron, O., Hansberg, A.: Volkmann, l.: k-domination and k-independence in graphs: a survey. Graphs Combin. 28, 1\u201355 (2012)","journal-title":"Graphs Combin."},{"key":"9764_CR9","doi-asserted-by":"crossref","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of edge dominating set problems, vol. 11 (2006)","DOI":"10.1007\/s10878-006-7908-0"},{"key":"9764_CR10","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-30216-2_3","volume-title":"Algorithms and Models for the Web-Graph, LNCS 3243","author":"C Cooper","year":"2004","unstructured":"Cooper, C., Klasing, R., Zito, M.: Dominating Sets in Web Graphs. In: Algorithms and Models for the Web-Graph, LNCS 3243, pp. 31\u201343. Springer, Heidelberg (2004)"},{"issue":"7","key":"9764_CR11","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1016\/j.jpdc.2005.12.010","volume":"66","author":"F Dai","year":"2006","unstructured":"Dai, F., Wu, J.: On Constructing k-connected k-dominating Set in Wireless Ad Hoc and Sensor Networks. J. Parallel Distrib. Comput. 66(7), 947\u2013958 (2006)","journal-title":"J. Parallel Distrib. Comput."},{"key":"9764_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-5242-3","volume-title":"Connected Dominating Set: Theory and Applications","author":"D-Z Du","year":"2013","unstructured":"Du, D.-Z., Wan, P.-J.: Connected Dominating Set: Theory and Applications. Springer, New York (2013)"},{"key":"9764_CR13","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1007\/978-1-4419-7997-1_42","volume-title":"Handbook of Combinatorial Optimization","author":"H Du","year":"2013","unstructured":"Du, H., Ding, L., Wu, W., Kim, D., Pardalos, P. M., Willson, J.: Connected Dominating Set in Wireless Networks. In: Pardalos, P.M., Du, D.-Z., Graham, R. (eds.) Handbook of Combinatorial Optimization, pp. 783\u2013833. Springer, New York (2013)"},{"issue":"2","key":"9764_CR14","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.h., Xiao, M.: New results on polynomial inapproximabilityand fixed parameter approximability of edge dominating set. Theory comput Syst. 56(2), 330\u2013346 (2015)","journal-title":"Theory comput Syst."},{"key":"9764_CR15","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/11847250_13","volume-title":"Proceedings 2Nd International Conference on Parameterized and Exact Computation","author":"H Fernau","year":"2006","unstructured":"Fernau, H.: EDGE DOMINATING SET: Efficient Enumeration-based Exact Algorithms Proceedings 2Nd International Conference on Parameterized and Exact Computation, pp. 142\u2013153. Springer, Heidelberg (2006)"},{"key":"9764_CR16","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-14031-0_6","volume-title":"Proceedings 16Th Annual International Conference on 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: Proceedings 16Th Annual International Conference on Computing and Combinatorics, pp. 34\u201343. Springer, Heidelberg (2010)"},{"issue":"2","key":"9764_CR17","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 Algoritms 7(2), 149\u2013167 (2009)","journal-title":"J. Discrete Algoritms"},{"key":"9764_CR18","first-page":"283","volume-title":"Graph Theory with Applications to Algorithms and Computer Science","author":"JF Fink","year":"1985","unstructured":"Fink, J. F., Jacobson, M.S.: n-Domination in Graphs. In: Alavi, Y., Chartrand, G., Lick, D. R., Wall, C. E., Lesniak, L. (eds.) Graph Theory with Applications to Algorithms and Computer Science, pp. 283\u2013300. John Wiley & Sons, Inc., New York (1985)"},{"key":"9764_CR19","first-page":"301","volume-title":"Graph Theory with Applications to Algorithms and Computer Science","author":"JF Fink","year":"1985","unstructured":"Fink, J. F., Jacobson, M. S.: On N-Domination, N-Dependence and Forbidden Subgraphs. In: Alavi, Y., Chartrand, G., Lick, D. R., Wall, C. E., authorLesniak, L. (eds.) Graph Theory with Applications to Algorithms and Computer Science, pp. 301\u2013311. John Wiley & Sons, Inc., New York (1985)"},{"issue":"2","key":"9764_CR20","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":"9764_CR21","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/978-3-319-08404-6_18","volume-title":"Algorithm Theory\u2013SWAT 2014, LNCS 8503","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: Algorithm Theory\u2013SWAT 2014, LNCS 8503, pp. 206\u2013216. Springer, Cham (2014)"},{"key":"9764_CR22","doi-asserted-by":"crossref","unstructured":"Gao, X., Zou, F., Kim, D., Du, D.-Z.: The Latest Researches on Dominating Problems in Wireless Sensor Network. In: Handbook on Sensor Networks, Pp. 197\u2013226. World Scientific (2010)","DOI":"10.1142\/9789812837318_0010"},{"key":"9764_CR23","doi-asserted-by":"crossref","unstructured":"Harary, F.: Graph theory. Addison-wesley, reading MA (1969)","DOI":"10.21236\/AD0705364"},{"key":"9764_CR24","volume-title":"Domination in Graphs, Advanced Topics","author":"TW Haynes","year":"1998","unstructured":"Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Domination in Graphs, Advanced Topics. Marcel Dekker, New York (1998)"},{"key":"9764_CR25","volume-title":"Fundamantals of Domination in Graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamantals of Domination in Graphs. Marcel Dekker, New York (1998)"},{"key":"9764_CR26","doi-asserted-by":"crossref","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 Ann. European Symp. on Algorithms, LNCS 855, pp. 424\u2013435. Springer (1994)","DOI":"10.1007\/BFb0049428"},{"key":"9764_CR27","doi-asserted-by":"crossref","unstructured":"Kim, D., Gao, X., Zou, F., Du, D.-Z.: Construction of Fault-Tolerant Virtual Backbones in Wireless Networks. In: Handbook on Security and Networks, pp. 488\u2013509. World Scientific (2011)","DOI":"10.1142\/9789814273046_0018"},{"key":"9764_CR28","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M. D.: Matching Theory. North-Holland, Amsterdam (1986)"},{"key":"9764_CR29","first-page":"647","volume-title":"Proceedings 2005 International Conference on Computational Science and Its Applications - Volume Part I","author":"M Ma\u0142afiejski","year":"2005","unstructured":"Ma\u0142afiejski, M., \u017byli\u0144ski, P.: Weakly Cooperative Guards in Grids. In: Proceedings 2005 International Conference on Computational Science and Its Applications - Volume Part I, pp. 647\u2013656. Springer, Heidelberg (2005)"},{"issue":"5","key":"9764_CR30","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"C Savage","year":"1982","unstructured":"Savage, C.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14(5), 233\u2013235 (1982)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9764_CR31","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."},{"issue":"1\u20133","key":"9764_CR32","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.tcs.2007.04.035","volume":"381","author":"W Shang","year":"2007","unstructured":"Shang, W., Wan, P., Yao, F., Hu, X.: Algorithms for minimum m-connected k-tuple dominating set problem. Theor. Comput. Sci. 381(1\u20133), 241\u2013247 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9764_CR33","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/s10878-014-9720-6","volume":"31","author":"Y Shi","year":"2016","unstructured":"Shi, Y., Zhang, Y., Zhang, Z., Wu, W.: A greedy algorithm for the minimum 2-connected m-fold dominating set problem. J. Comb. Optim. 31(1), 136\u2013151 (2016)","journal-title":"J. Comb. Optim."},{"issue":"1\u20133","key":"9764_CR34","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.tcs.2007.05.025","volume":"385","author":"MT Thai","year":"2007","unstructured":"Thai, M. T., Zhang, N., Tiwari, R., Xu, X.: On approximation algorithms of k-connected m-dominating sets in disk graphs. Theor. Comput. Sci. 385(1\u20133), 49\u201359 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9764_CR35","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/1374618.1374631","volume-title":"Proceedings 9Th ACM International Symposium on Mobile Ad Hoc Networking and Computing","author":"Y Wu","year":"2008","unstructured":"Wu, Y., Li, Y.: Construction Algorithms for K-Connected M-Dominating Sets in Wireless Sensor Networks. In: Proceedings 9Th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 83\u201390. ACM, New York (2008)"},{"key":"9764_CR36","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":"9764_CR37","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."},{"issue":"1","key":"9764_CR38","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/s10878-013-9638-4","volume":"28","author":"J Zhou","year":"2014","unstructured":"Zhou, J., Zhang, Z., Wu, W., Xing, K.: A greedy algorithm for the fault-tolerant connected dominating set in a general graph. J. Comb. Optim. 28(1), 310\u2013319 (2014)","journal-title":"J. Comb. Optim."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9764-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9764-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9764-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T04:11:07Z","timestamp":1658895067000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9764-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,3]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["9764"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9764-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,4,3]]},"assertion":[{"value":"3 April 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}