{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:06:28Z","timestamp":1742918788246,"version":"3.40.3"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319130743"},{"type":"electronic","value":"9783319130750"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13075-0_16","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:37:06Z","timestamp":1415983026000},"page":"195-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Minimum-Cost $$b$$-Edge Dominating Sets on Trees"],"prefix":"10.1007","author":[{"given":"Takehiro","family":"Ito","sequence":"first","affiliation":[]},{"given":"Naonori","family":"Kakimura","sequence":"additional","affiliation":[]},{"given":"Naoyuki","family":"Kamiyama","sequence":"additional","affiliation":[]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[]},{"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,8]]},"reference":[{"issue":"1\u20133","key":"16_CR1","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-edge dominating set problem. Theor. Comput. Sci. 385(1\u20133), 202\u2013213 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"16_CR2","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"},{"issue":"1","key":"16_CR3","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/s00453-011-9558-6","volume":"62","author":"A Berger","year":"2012","unstructured":"Berger, A., Parekh, O.: Erratum to: Linear Time Algorithms for Generalized Edge Dominating Set Problems. Algorithmica 62(1), 633\u2013634 (2012)","journal-title":"Algorithmica"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Dadush, D., Peikert, C., Vempala, S.: Enumerative lattice algorithms in any norm via M-ellipsoid coverings. In: FOCS, pp. 580\u2013589 (2011)","DOI":"10.1109\/FOCS.2011.31"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Dadush, D., Vempala, S.: Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms. In: SODA, pp. 1445\u20131456 (2012)","DOI":"10.1137\/1.9781611973099.114"},{"issue":"3","key":"16_CR6","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0166-218X(00)00383-8","volume":"118","author":"T Fujito","year":"2002","unstructured":"Fujito, T., Nagamochi, H.: A $$2$$-approximation algorithm for the minimum weight edge dominating set problem. Discrete Appl. Math. 118(3), 199\u2013207 (2002)","journal-title":"Discrete Appl. Math."},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer (2004)","DOI":"10.1007\/978-3-540-24777-7"},{"issue":"4","key":"16_CR8","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"16_CR9","unstructured":"Parekh, O.: Edge dominating and hypomatchable sets. In: SODA, 287\u2013291 (2002)"},{"key":"16_CR10","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. John Wiley & Sons (1986)"},{"issue":"2","key":"16_CR11","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"\u00c9 Tardos","year":"1986","unstructured":"Tardos, \u00c9.: A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research 34(2), 250\u2013256 (1986)","journal-title":"Operations Research"},{"key":"16_CR12","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer (2001)"},{"issue":"3","key":"16_CR13","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","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13075-0_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T03:40:00Z","timestamp":1676000400000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13075-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130743","9783319130750"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13075-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"8 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}