{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T07:35:49Z","timestamp":1743060949946,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319487489"},{"type":"electronic","value":"9783319487496"}],"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":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-48749-6_6","type":"book-chapter","created":{"date-parts":[[2016,10,30]],"date-time":"2016-10-30T08:16:59Z","timestamp":1477815419000},"page":"77-91","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computing a Tree Having a Small Vertex Cover"],"prefix":"10.1007","author":[{"given":"Takuro","family":"Fukunaga","sequence":"first","affiliation":[]},{"given":"Takanori","family":"Maehara","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60, 6 (2013)","journal-title":"J. ACM"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Olver, N., Rothvo\u00df, T., Zenklusen, R.: Matroids and integrality gaps for hypergraphic steiner tree relaxations. In: STOC, pp. 1161\u20131176 (2012)","DOI":"10.1145\/2213977.2214081"},{"key":"6_CR3","unstructured":"Klein, P.N., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. In: IPCO, pp. 323\u2013332 (1993)"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Perlman, R.J.: An algorithm for distributed computation of a spanningtree in an extended LAN. In: SIGCOMM, pp. 44\u201353 (1985)","DOI":"10.1145\/318951.319004"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Panigrahi, D.: Survivable network design problems in wireless networks. In: SODA, pp. 1014\u20131027 (2011)","DOI":"10.1137\/1.9781611973082.78"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/978-3-662-48971-0_32","volume-title":"Algorithms and Computation","author":"E Angel","year":"2015","unstructured":"Angel, E., Bampis, E., Chau, V., Kononov, A.: Min-power covering problems. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 367\u2013377. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48971-0_32"},{"key":"6_CR7","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2601070","volume":"10","author":"ED Demaine","year":"2014","unstructured":"Demaine, E.D., Hajiaghayi, M., Klein, P.N.: Node-weighted Steiner tree and group Steiner tree in planar graphs. ACM Trans. Algorithms 10, 13 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/s10878-009-9229-6","volume":"18","author":"F Zou","year":"2009","unstructured":"Zou, F., Li, X., Gao, S., Wu, W.: Node-weighted Steiner tree approximation in unit disk graphs. J. Comb. Opt. 18, 342\u2013349 (2009)","journal-title":"J. Comb. Opt."},{"key":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-540-85097-7_26","volume-title":"Combinatorial Optimization and Applications","author":"F Zou","year":"2008","unstructured":"Zou, F., Li, X., Kim, D., Wu, W.: Two constant approximation algorithms for node-weighted steiner tree in unit disk graphs. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol. 5165, pp. 278\u2013285. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-85097-7_26"},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/11830924_3","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C Amb\u00fchl","year":"2006","unstructured":"Amb\u00fchl, C., Erlebach, T., Mihal\u00e1k, M., Nunkesser, M.: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX\/RANDOM -2006. LNCS, vol. 4110, pp. 3\u201314. Springer, Heidelberg (2006). doi: 10.1007\/11830924_3"},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-319-21398-9_15","volume-title":"Computing and Combinatorics","author":"L Huang","year":"2015","unstructured":"Huang, L., Li, J., Shi, Q.: Approximation algorithms for the connected sensor cover problem. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 183\u2013196. Springer, Heidelberg (2015). doi: 10.1007\/978-3-319-21398-9_15"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.tcs.2009.06.022","volume":"412","author":"F Zou","year":"2011","unstructured":"Zou, F., Wang, Y., Xu, X., Li, X., Du, H., Wan, P., Wu, W.: New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theor. Comp. Sci. 412, 198\u2013208 (2011)","journal-title":"Theor. Comp. Sci."},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1016\/j.jcss.2010.02.001","volume":"76","author":"F Eisenbrand","year":"2010","unstructured":"Eisenbrand, F., Grandoni, F., Rothvo\u00df, T., Sch\u00e4fer, G.: Connected facility location via random facility sampling and core detouring. J. Comp. Sys. Sci. 76, 709\u2013726 (2010)","journal-title":"J. Comp. Sys. Sci."},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C Swamy","year":"2004","unstructured":"Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica 40, 245\u2013269 (2004)","journal-title":"Algorithmica"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1002\/net.10097","volume":"42","author":"X Cheng","year":"2003","unstructured":"Cheng, X., Huang, X., Li, D., Wu, W., Du, D.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42, 202\u2013208 (2003)","journal-title":"Networks"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374\u2013387 (1998)","journal-title":"Algorithmica"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02579141","volume":"4","author":"AV Kostochka","year":"1984","unstructured":"Kostochka, A.V.: Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica 4, 307\u2013316 (1984)","journal-title":"Combinatorica"},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1006\/jctb.2000.2013","volume":"81","author":"A Thomason","year":"2001","unstructured":"Thomason, A.: The extremal function for complete minors. J. Comb. Theory Ser. B 81, 318\u2013338 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-319-18263-6_12","volume-title":"Approximation and Online Algorithms","author":"GD Fonseca","year":"2015","unstructured":"Fonseca, G.D., S\u00e1, V.G.P., Figueiredo, C.M.H.: Linear-time approximation algorithms for unit disk graphs. In: Bampis, E., Svensson, O. (eds.) WAOA 2014. LNCS, vol. 8952, pp. 132\u2013143. Springer, Heidelberg (2015). doi: 10.1007\/978-3-319-18263-6_12"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48749-6_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,27]],"date-time":"2020-09-27T01:30:46Z","timestamp":1601170246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48749-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319487489","9783319487496"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48749-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"31 October 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 December 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 December 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conference.cs.cityu.edu.hk\/cocoa2016\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}