{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T03:10:53Z","timestamp":1785467453650,"version":"3.56.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,7,15]],"date-time":"2014-07-15T00:00:00Z","timestamp":1405382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s10878-014-9772-7","type":"journal-article","created":{"date-parts":[[2014,7,13]],"date-time":"2014-07-13T23:59:25Z","timestamp":1405295965000},"page":"370-386","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["On the clustered Steiner tree problem"],"prefix":"10.1007","volume":"30","author":[{"given":"Bang Ye","family":"Wu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chen-Wan","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,7,15]]},"reference":[{"issue":"3","key":"9772_CR1","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"Agrawal A, Klein P, Ravi R (1995) When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J Comput 24(3):440\u2013456","journal-title":"SIAM J Comput"},{"issue":"23","key":"9772_CR2","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1016\/j.ipl.2012.08.020","volume":"112","author":"X Bao","year":"2012","unstructured":"Bao X, Liu Z (2012) An improved approximation algorithm for the clustered traveling salesman problem. Inform Process Lett 112(23):908\u2013910","journal-title":"Inform Process Lett"},{"key":"9772_CR3","doi-asserted-by":"crossref","unstructured":"Byrka J, Grandoni F, Rothvo\u00df T, Sanit\u00e0 L (2010) An improved LP-based approximation for Steiner tree. Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC10ACM, New York, USA, pp 583\u2013592","DOI":"10.1145\/1806689.1806769"},{"key":"9772_CR4","doi-asserted-by":"crossref","unstructured":"Chen YH, Lu CL, Tang CY (2003) On the full and bottleneck full Steiner tree problems. In: Warnow T, Zhu B (eds) Computing and Combinatorics, COCOON03, vol 2697., Lecture Notes in Computer ScienceSpringer, Berlin Heidelberg, pp 122\u2013129","DOI":"10.1007\/3-540-45071-8_14"},{"key":"9772_CR5","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. The MIT Press, Cambridge","edition":"2"},{"issue":"1","key":"9772_CR6","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/s10878-013-9611-2","volume":"27","author":"W Ding","year":"2014","unstructured":"Ding W, Xue G (2014) Minimum diameter cost-constrained Steiner trees. J Comb Optim 27(1):32\u201348","journal-title":"J Comb Optim"},{"key":"9772_CR7","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.ipl.2003.09.014","volume":"89","author":"DE Drake","year":"2004","unstructured":"Drake DE, Hougardy S (2004) On approximation algorithms for the terminal Steiner tree problem. Inform Process Lett 89:15\u201318","journal-title":"Inform Process Lett"},{"issue":"4","key":"9772_CR8","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey MR, Graham RL, Johnson DS (1977) The complexity of computing Steiner minimal trees. SIAM J Appl Math 32(4):835\u2013859","journal-title":"SIAM J Appl Math"},{"issue":"4","key":"9772_CR9","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey MR, Johnson DS (1977) The rectilinear Steiner tree problem is NP-Complete. SIAM J Appl Math 32(4):826\u2013834","journal-title":"SIAM J Appl Math"},{"key":"9772_CR10","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co, New York"},{"key":"9772_CR11","unstructured":"Garg N, Konjevod G, Ravi R (1998) A polylogarithmic approximation algorithm for the group Steiner tree problem. Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA98SIAM, Philadelphia, PA, USA, pp 253\u2013259"},{"key":"9772_CR12","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/s004530010045","volume":"28","author":"N Guttmann-beck","year":"2000","unstructured":"Guttmann-beck N, Hassin R, Khuller S, Raghavachari B (2000) Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28:422\u2013437","journal-title":"Algorithmica"},{"key":"9772_CR13","doi-asserted-by":"crossref","unstructured":"Hsieh SY, Yang SC (2007) Approximating the selected-internal Steiner tree. Theor Comput Sci 381(1\u20133): 288\u2013291","DOI":"10.1016\/j.tcs.2007.05.035"},{"issue":"1","key":"9772_CR14","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s10878-005-5487-0","volume":"9","author":"TS Hsu","year":"2005","unstructured":"Hsu TS, Tsai KH, Wang DW, Lee DT (2005) Two variations of the minimum Steiner problem. J Comb Optim 9(1):101\u2013120","journal-title":"J Comb Optim"},{"issue":"1","key":"9772_CR15","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.jco.2012.08.005","volume":"29","author":"CW Huang","year":"2013","unstructured":"Huang CW, Lee CW, Gao HM, Hsieh SY (2013) The internal Steiner tree problem: hardness and approximations. J Complex 29(1):27\u201343","journal-title":"J Complex"},{"key":"9772_CR16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"R Karp","year":"1972","unstructured":"Karp R (1972) Reducibility among combinatorial problems. In: Miller R, Thatcher J (eds) Complexity of computer computations. Plenum Press, New York, pp 85\u2013103"},{"issue":"3","key":"9772_CR17","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/s00453-009-9301-8","volume":"56","author":"X Li","year":"2010","unstructured":"Li X, Zou F, Huang Y, Kim D, Wu W (2010) A better constant-factor approximation for selected-internal Steiner minimum tree. Algorithmica 56(3):333\u2013341","journal-title":"Algorithmica"},{"issue":"2","key":"9772_CR18","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0020-0190(02)00227-2","volume":"84","author":"GH Lin","year":"2002","unstructured":"Lin GH, Xue G (2002) On the terminal Steiner tree problem. Inform Process Lett 84(2):103\u2013107","journal-title":"Inform Process Lett"},{"key":"9772_CR19","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0304-3975(03)00209-3","volume":"306","author":"CL Lu","year":"2003","unstructured":"Lu CL, Tang CY, Lee RCT (2003) The full Steiner tree problem. Theor Comput Sci 306:55\u201367","journal-title":"Theor Comput Sci"},{"key":"9772_CR20","doi-asserted-by":"crossref","unstructured":"Martinez F, de Pina J, Soares J (2007) Algorithms for terminal Steiner trees. Theor Comput Sci 389(1\u20132): 133\u2013142","DOI":"10.1016\/j.tcs.2007.08.001"},{"key":"9772_CR21","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G Robins","year":"2005","unstructured":"Robins G, Zelikovsky A (2005) Tighter bounds for graph Steiner tree approximation. SIAM J Discret Math 19:122\u2013134","journal-title":"SIAM J Discret Math"},{"key":"9772_CR22","volume-title":"Spanning trees and optimization problems","author":"BY Wu","year":"2004","unstructured":"Wu BY, Chao KM (2004) Spanning trees and optimization problems. Chapman and Hall, Boca Raton"},{"issue":"5","key":"9772_CR23","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A Zelikovsky","year":"1993","unstructured":"Zelikovsky A (1993) An 11\/6-approximation algorithm for the network Steiner problem. Algorithmica 9(5):463\u2013470","journal-title":"Algorithmica"},{"issue":"4","key":"9772_CR24","doi-asserted-by":"crossref","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 (2009) Node-weighted Steiner tree approximation in unit disk graphs. J Comb Optim 18(4):342\u2013349","journal-title":"J Comb Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9772-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-014-9772-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9772-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:23:24Z","timestamp":1559262204000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-014-9772-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,15]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9772"],"URL":"https:\/\/doi.org\/10.1007\/s10878-014-9772-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,15]]}}}