{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:42:31Z","timestamp":1760708551590},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,4,3]],"date-time":"2013-04-03T00:00:00Z","timestamp":1364947200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1007\/s10878-013-9611-2","type":"journal-article","created":{"date-parts":[[2013,4,2]],"date-time":"2013-04-02T16:00:14Z","timestamp":1364918414000},"page":"32-48","source":"Crossref","is-referenced-by-count":7,"title":["Minimum diameter cost-constrained Steiner trees"],"prefix":"10.1007","volume":"27","author":[{"given":"Wei","family":"Ding","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guoliang","family":"Xue","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,4,3]]},"reference":[{"key":"9611_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph theory with application","author":"JA Bondy","year":"1976","unstructured":"Bondy JA, Murty USR (1976) Graph theory with application. Macmillan, London"},{"key":"9611_CR2","unstructured":"Chan TM (2002) Semi-online maintenance of geometric optima and measures. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), 474\u2013483."},{"key":"9611_CR3","unstructured":"Chen YH (2011) An improved approximation algorithm for the terminal Steiner tree problem. B. Murgante et al. (eds): ICCSA 2011. Part III, LNCS 6784, 141\u2013151"},{"key":"9611_CR4","unstructured":"Deo N, Abdalla A (2000) Computing a diameter-constrained minimum spanning tree in parallel. In: Algorithms and complexity. LNCS. 1767, 17\u201331"},{"key":"9611_CR5","doi-asserted-by":"crossref","unstructured":"Ding W (2010) Many-to-many multicast routing under a fixed topology: basic architecture, problems and algorithms. In: First international conference on networking and distributed computing (ICNDC\u2019 2010), pp. 128\u2013132.","DOI":"10.1109\/ICNDC.2010.34"},{"issue":"4","key":"9611_CR6","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1142\/S179383091100136X","volume":"3","author":"W Ding","year":"2011","unstructured":"Ding W, Lin G, Xue G (2011) Diameter-constrained Steiner trees. Discret Math Algorithms Appl 3(4):491\u2013502","journal-title":"Discret Math Algorithms Appl"},{"key":"9611_CR7","doi-asserted-by":"crossref","unstructured":"Ding W, Qiu K (2013) Algorithms for the minimum diameter terminal Steiner tree problem. J Combin Optim. doi: 10.1007\/s10878-012-9591-7","DOI":"10.1007\/s10878-012-9591-7"},{"key":"9611_CR8","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/j.tcs.2009.08.003","volume":"412","author":"W Ding","year":"2011","unstructured":"Ding W, Xue G (2011) A linear time algorithm for computing a most reliable source on a tree network with faulty nodes. Theor Comput Sci 412:225\u2013232","journal-title":"Theor Comput Sci"},{"key":"9611_CR9","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, Hougrady S (2004) On approximation algorithms for the terminal Steiner tree problem. Inf Process Lett 89:15\u201318","journal-title":"Inf Process Lett"},{"key":"9611_CR10","doi-asserted-by":"crossref","DOI":"10.1142\/6729","volume-title":"Steiner tree problems in computer communication networks","author":"D Du","year":"2008","unstructured":"Du D, Hu X (2008) Steiner tree problems in computer communication networks. World Scientific Publishing Co. Pte. Ltd., Singapore"},{"key":"9611_CR11","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/S0020-0190(03)00285-0","volume":"87","author":"B Fuchs","year":"2003","unstructured":"Fuchs B (2003) A note on the terminal Steiner tree problem. Inf Process Lett 87:219\u2013220","journal-title":"Inf Process Lett"},{"key":"9611_CR12","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. Freeman, San Francisco, CA"},{"key":"9611_CR13","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.10069","volume":"41","author":"L Gouveia","year":"2003","unstructured":"Gouveia L, Magnanti TL (2003) Network flow models for designing diameter-constrained minimum spanning and Steiner trees. Networks 41:159\u2013173","journal-title":"Networks"},{"key":"9611_CR14","unstructured":"Gudmundsson J, Haverkort H, Park SM, Shin CS, Wolff A (2002) Approximating the geometric minimum-diameter spanning tree. In: Proc. 18th European Workshop on Computational Geometry (EWCG 2002), 41\u201345."},{"key":"9611_CR15","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R Hassin","year":"1992","unstructured":"Hassin R (1992) Approximation schemes for the restricted shortest path problem. Math Oper Res 17:36\u201342","journal-title":"Math Oper Res"},{"key":"9611_CR16","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(94)00183-Y","volume":"53","author":"R Hassin","year":"1995","unstructured":"Hassin R, Tamir A (1995) On the minimum diameter spanning tree problem. Inf Process Lett 53:109\u2013111","journal-title":"Inf Process Lett"},{"key":"9611_CR17","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1137\/0220060","volume":"20","author":"JM Ho","year":"1991","unstructured":"Ho JM, Lee DT, Chang CH, Wong CK (1991) Minimum diameter spanning trees and related problems. SIAM J Comput 20:987\u2013997","journal-title":"SIAM J Comput"},{"key":"9611_CR18","volume-title":"The Steiner tree problem. Annals of Disc. Math. 53","author":"FK Hwang","year":"1992","unstructured":"Hwang FK, Richards DS, Winter P (1992) The Steiner tree problem. Annals of Disc. Math. 53. North-Holland, Amsterdam"},{"issue":"4","key":"9611_CR19","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O Ibarra","year":"1975","unstructured":"Ibarra O, Kim C (1975) Fast approximation algorithms for the knapsack and sum of subset problems. JACM 22(4):463\u2013468","journal-title":"JACM"},{"key":"9611_CR20","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0020-0190(02)00227-2","volume":"84","author":"G Lin","year":"2002","unstructured":"Lin G, Xue G (2002) On the terminal Steiner problem. Inf Process Lett 84:103\u2013107","journal-title":"Inf Process Lett"},{"key":"9611_CR21","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.tcs.2007.08.001","volume":"389","author":"FV Martineza","year":"2007","unstructured":"Martineza FV, Pinab JCD, Soares J (2007) Algorithm for terminal Steiner trees. Theor Comput Sci 389:133\u2013142","journal-title":"Theor Comput Sci"},{"issue":"1","key":"9611_CR22","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1006\/jagm.1998.0930","volume":"28","author":"MV Marathe","year":"1998","unstructured":"Marathe MV, Ravi R, Sundaram R, Ravi SS, Rosenkrantz DJ, Hunt III HB (1998) Bicriteria network design problems. J Algorithms 28(1):142\u2013171","journal-title":"J Algorithms"},{"key":"9611_CR23","unstructured":"Robins G, Zelikovsky A (2000) Improved Steiner tree approximation in graphs. In: Proc. of the 11th Annual ACM-SIAM Symposium on discrete algorithm (SODA 2000), 770\u2013779."},{"key":"9611_CR24","unstructured":"Dos Santos AC, Lucena A, Ribeiro CC (2004) Solving diameter constrained minimum spanning tree problems in dense graphs. In: Experimental and efficient algorithms. LNCS. 3059, 458\u2013467"},{"key":"9611_CR25","first-page":"70","volume":"35","author":"S Sahni","year":"1977","unstructured":"Sahni S (1977) General techniques for combinatorial approximations. Oper Res 35:70\u201379","journal-title":"Oper Res"},{"issue":"4","key":"9611_CR26","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/s00453-003-1056-z","volume":"38","author":"MJ Spriggs","year":"2004","unstructured":"Spriggs MJ, Keil JM, Bespamyatnikh S, Segal M, Snoeyink J (2004) Computing a $$(1+\\epsilon )$$ -approximate geometric minimum-diameter spanning tree. Algorithmica 38(4):577\u2013589","journal-title":"Algorithmica"},{"key":"9611_CR27","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0167-6377(96)00021-1","volume":"19","author":"A Tamir","year":"1996","unstructured":"Tamir A (1996) An $$O(pn^2)$$ algorithm for the $$p$$ -median and related problems on tree graphs. Oper Res Lett 19:59\u201364","journal-title":"Oper Res Lett"},{"key":"9611_CR28","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV (2001) Approximation algorithms. Springer, Berlin"},{"key":"9611_CR29","unstructured":"Wang L, Jia X (1999) Note fixed topology Steiner trees and spanning forests. Theor Comput Sci 215 (1\u20132):359\u2013370"},{"issue":"1","key":"9611_CR30","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s00453-004-1119-9","volume":"41","author":"G Xue","year":"2004","unstructured":"Xue G, Xiao W (2004) A polynomial time approximation scheme for minimum cost delay-constrained multicast tree under a Steiner topology. Algorithmica 41(1):53\u201372","journal-title":"Algorithmica"},{"key":"9611_CR31","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1109\/TNET.2007.900712","volume":"16","author":"G Xue","year":"2008","unstructured":"Xue G, Zhang W, Tang J, Thulasiraman K (2008) Polynomial time approximation algorithms for multi-constrained QoS routing. IEEE\/ACM Trans Netw 16:656\u2013669","journal-title":"IEEE\/ACM Trans Netw"},{"issue":"5","key":"9611_CR32","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A Zelikovsky","year":"1993","unstructured":"Zelikovsky A (1993) An $$\\frac{11}{6}$$ -approximation algorithm for the network Steiner problem. Algorithmica 9(5):463\u2013470","journal-title":"Algorithmica"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9611-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9611-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9611-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,11]],"date-time":"2019-07-11T17:33:13Z","timestamp":1562866393000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9611-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,3]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9611"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9611-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,3]]}}}