{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:32:15Z","timestamp":1743006735366,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319037790"},{"type":"electronic","value":"9783319037806"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"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":[[2013]]},"DOI":"10.1007\/978-3-319-03780-6_6","type":"book-chapter","created":{"date-parts":[[2013,11,21]],"date-time":"2013-11-21T01:13:18Z","timestamp":1384996398000},"page":"60-71","source":"Crossref","is-referenced-by-count":1,"title":["On the Clustered Steiner Tree Problem"],"prefix":"10.1007","author":[{"given":"Bang Ye","family":"Wu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"6_CR1","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A. Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: An approximation algorithm for the generalized Steiner problem in networks. SIAM Journal on Computing\u00a024(3), 445\u2013456 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1016\/j.ipl.2012.08.020","volume":"112","author":"X. Bao","year":"2012","unstructured":"Bao, X., Liu, Z.: An improved approximation algorithm for the clustered traveling salesman problem. Information Processing Letters\u00a0112, 908\u2013910 (2012)","journal-title":"Information Processing Letters"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e1, L.: An improved LP-based approximation for Steiner tree. In: Proc. 42nd ACM Symposium on Theory of Computing, pp. 583\u2013592 (2010)","DOI":"10.1145\/1806689.1806769"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/3-540-45071-8_14","volume-title":"Computing and Combinatorics","author":"Y.H. Chen","year":"2003","unstructured":"Chen, Y.H., Lu, C.L., Tang, C.Y.: On the full and bottleneck full Steiner tree problems. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol.\u00a02697, pp. 122\u2013129. Springer, Heidelberg (2003)"},{"key":"6_CR5","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press and McGraw-Hill (2001)"},{"issue":"1","key":"6_CR6","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ipl.2003.09.014","volume":"89","author":"D.E. Drake","year":"2004","unstructured":"Drake, D.E., Hougardy, S.: On approximation algorithms for the terminal Steiner tree problem. Information Processing Letters\u00a089(1), 15\u201318 (2004)","journal-title":"Information Processing Letters"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/S0020-0190(03)00285-0","volume":"87","author":"B. Fuchs","year":"2003","unstructured":"Fuchs, B.: A note on the terminal Steiner tree problem. Information Processing Letters\u00a087, 219\u2013220 (2003)","journal-title":"Information Processing Letters"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Graham, R., Johnson, D.: The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics\u00a032, 835\u2013859 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.: The rectilinear Steiner problem is NP-complete. SIAM Journal on Applied Mathematics\u00a032, 826\u2013834 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"6_CR10","volume-title":"Computers and Intractability: A Guide to The Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to The Theory of NP-Completeness. Freeman, NewYork (1979)"},{"key":"6_CR11","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner problem. In: Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, pp. 253\u2013259 (1998)"},{"key":"6_CR12","doi-asserted-by":"publisher","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.: Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica\u00a028, 422\u2013437 (2000)","journal-title":"Algorithmica"},{"issue":"1-3","key":"6_CR13","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/j.tcs.2007.05.035","volume":"381","author":"S.Y. Hsieh","year":"2007","unstructured":"Hsieh, S.Y., Yang, S.C.: Approximating the selected-internal Steiner tree. Theoretical Computer Science\u00a0381(1-3), 288\u2013291 (2007)","journal-title":"Theoretical Computer Science"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.jco.2012.08.005","volume":"29","author":"C.W. Huang","year":"2013","unstructured":"Huang, C.W., Lee, C.W., Gao, H.M., Hsieh, S.Y.: The internal Steiner tree problem: Hardness and approximations. Journal of Complexity\u00a029, 27\u201343 (2013)","journal-title":"Journal of Complexity"},{"key":"6_CR15","doi-asserted-by":"publisher","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.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"6_CR16","doi-asserted-by":"publisher","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.: A better constant-factor approximation for selected-internal Steiner minimum tree. Algorithmica\u00a056, 333\u2013341 (2010)","journal-title":"Algorithmica"},{"issue":"2","key":"6_CR17","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0020-0190(02)00227-2","volume":"84","author":"G.H. Lin","year":"2002","unstructured":"Lin, G.H., Xue, G.L.: On the terminal Steiner tree problem. Information Processing Letters\u00a084(2), 103\u2013107 (2002)","journal-title":"Information Processing Letters"},{"issue":"1-3","key":"6_CR18","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0304-3975(03)00209-3","volume":"306","author":"C.L. Lu","year":"2003","unstructured":"Lu, C.L., Tang, C.Y., Lee, R.C.T.: The full Steiner tree problem. Theoretical Computer Science\u00a0306(1-3), 55\u201367 (2003)","journal-title":"Theoretical Computer Science"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.tcs.2007.08.001","volume":"389","author":"F.V. Martinez","year":"2007","unstructured":"Martinez, F.V., de Pina, J.C., Soares, J.: Algorithms for terminal Steiner trees. Theoretical Computer Science\u00a0389, 133\u2013142 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"6_CR20","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G. Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM Journal on Discrete Mathematics\u00a019(1), 122\u2013134 (2005)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/978-3-642-36694-9_31","volume-title":"Integer Programming and Combinatorial Optimization","author":"A. Seb\u0151","year":"2013","unstructured":"Seb\u0151, A.: Eight-fifth approximation for the path TSP. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol.\u00a07801, pp. 362\u2013374. Springer, Heidelberg (2013)"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Wu, B.Y., Chao, K.M.: Spanning Trees and Optimization Problems. Chapman & Hall (2004)","DOI":"10.1201\/9780203497289"},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A. Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: An 11\/6-approximation algorithm for the network Steiner problem. Algorithmica\u00a09, 463\u2013470 (1993)","journal-title":"Algorithmica"}],"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-03780-6_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T08:39:43Z","timestamp":1558687183000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03780-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319037790","9783319037806"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03780-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}