{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:47Z","timestamp":1740122447775,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T00:00:00Z","timestamp":1654473600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T00:00:00Z","timestamp":1654473600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11861075"],"award-info":[{"award-number":["11861075"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013047","name":"Cultivating Plan Program for the Leader in Science and Technology of Yunnan Province","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100013047","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008871","name":"Yunnan Provincial Science and Technology Department","doi-asserted-by":"publisher","award":["2018FY001014"],"award-info":[{"award-number":["2018FY001014"]}],"id":[{"id":"10.13039\/501100008871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007846","name":"Yunnan Provincial Department of Education","doi-asserted-by":"crossref","award":["2019Y0022"],"award-info":[{"award-number":["2019Y0022"]}],"id":[{"id":"10.13039\/501100007846","id-type":"DOI","asserted-by":"crossref"}]},{"name":"program for innovative research team (in science and technology) in universities of yunnan province","award":["C176240111009"],"award-info":[{"award-number":["C176240111009"]}]},{"DOI":"10.13039\/501100001809","name":"national natural science foundation of china","doi-asserted-by":"publisher","award":["11461081"],"award-info":[{"award-number":["11461081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s10898-022-01163-x","type":"journal-article","created":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T02:02:21Z","timestamp":1654480941000},"page":"687-714","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for solving the line-capacitated minimum Steiner tree problem"],"prefix":"10.1007","volume":"84","author":[{"given":"Jianping","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wencheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junran","family":"Lichen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suding","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pengxiang","family":"Pan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,6]]},"reference":[{"issue":"5","key":"1163_CR1","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"E Allender","year":"2009","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM J. Comput. 38(5), 1987\u20132006 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1163_CR2","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0167-6377(87)90012-5","volume":"6","author":"K Altinkemer","year":"1987","unstructured":"Altinkemer, K., Gavish, B.: Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper. Res. Lett. 6(4), 149\u2013158 (1987)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"1163_CR3","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1287\/mnsc.34.3.331","volume":"34","author":"K Altinkemer","year":"1988","unstructured":"Altinkemer, K., Gavish, B.: Heuristics with constant error guarantees for the design of tree networks. Manag. Sci. 34(3), 331\u2013341 (1988)","journal-title":"Manag. Sci."},{"issue":"1","key":"1163_CR4","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1111\/j.1749-6632.1985.tb14564.x","volume":"440","author":"FRK Chung","year":"1985","unstructured":"Chung, F.R.K., Graham, R.L.: A new bound for Euclidean Steiner minimal trees. Ann. N.Y. Acad. Sci. 440(1), 328\u2013346 (1985)","journal-title":"Ann. N.Y. Acad. Sci."},{"key":"1163_CR5","doi-asserted-by":"publisher","DOI":"10.1142\/6729","volume-title":"Steiner Tree Problems in Computer Communication Networks","author":"DZ Du","year":"2008","unstructured":"Du, D.Z., Hu, X.D.: Steiner Tree Problems in Computer Communication Networks. World Scientific, Singapore (2008)"},{"issue":"1","key":"1163_CR6","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with (0, 1)-vertices. J. Res. Natl. Bur. Stand. 69(1), 125\u2013130 (1965)","journal-title":"J. Res. Natl. Bur. Stand."},{"issue":"3","key":"1163_CR7","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"1163_CR8","doi-asserted-by":"crossref","unstructured":"Gabow H.N.: Data structures for weighted matching and extensions to $$b$$-matching and $$f$$-factors. ACM Trans. Algorithms 14(3), Art.39, 80 (2018)","DOI":"10.1145\/3183369"},{"issue":"2","key":"1163_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"HN Gabow","year":"1986","unstructured":"Gabow, H.N., Galil, Z., Spencer, T., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2), 109\u2013122 (1986)","journal-title":"Combinatorica"},{"issue":"4","key":"1163_CR10","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32(4), 835\u2013859 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"1163_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)"},{"issue":"3","key":"1163_CR12","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s00453-003-1069-7","volume":"38","author":"RR Hassin","year":"2004","unstructured":"Hassin, R.R., Ravi, R., Salman, F.S.: Approximation algorithms for a capacitated network design problem. Algorithmica 38(3), 417\u2013431 (2004)","journal-title":"Algorithmica"},{"issue":"1","key":"1163_CR13","first-page":"124","volume":"18","author":"J Holby","year":"2017","unstructured":"Holby, J.: Variations on the Euclidean Steiner tree problem and algorithms. Rose-Hulman Undergrad. Math. J. 18(1), 124\u2013155 (2017)","journal-title":"Rose-Hulman Undergrad. Math. J."},{"issue":"1","key":"1163_CR14","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"FK Hwang","year":"1976","unstructured":"Hwang, F.K.: On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math. 30(1), 104\u2013114 (1976)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"1163_CR15","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/net.3230220105","volume":"22","author":"FK Hwang","year":"1992","unstructured":"Hwang, F.K., Richards, D.S.: Steiner tree problem. Networks 22(1), 55\u201389 (1992)","journal-title":"Networks"},{"issue":"4","key":"1163_CR16","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.ipl.2004.04.007","volume":"91","author":"R Jothi","year":"2004","unstructured":"Jothi, R., Raghavachari, B.: Survivable network design: the capacitated minimum spanning network problem. Inf. Process. Lett. 91(4), 183\u2013190 (2004)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1163_CR17","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1145\/1103963.1103967","volume":"1","author":"R Jothi","year":"2005","unstructured":"Jothi, R., Raghavachari, B.: Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design. ACM Trans. Algorithms 1(2), 265\u2013282 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"1163_CR18","unstructured":"Kleinberg, J., Tardos, \u00c9.: Algorithm Design. Pearson (2006)"},{"key":"1163_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"B Korte","year":"2012","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 5th edn. Springer, Berlin (2012)","edition":"5"},{"issue":"1","key":"1163_CR20","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J Kruskal","year":"1956","unstructured":"Kruskal, J.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"1163_CR21","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1007\/s10878-019-00492-0","volume":"39","author":"JP Li","year":"2020","unstructured":"Li, J.P., Liu, S.D., Lichen, J.R., Wang, W.C., Zheng, Y.J.: Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem. J. Comb. Optim. 39, 492\u2013508 (2020)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"1163_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/net.22005","volume":"77","author":"I Ljubi\u0107","year":"2021","unstructured":"Ljubi\u0107, I.: Solving Steiner trees: recent advances, challenges, and perspectives. Networks 77(2), 177\u2013204 (2021)","journal-title":"Networks"},{"key":"1163_CR23","volume-title":"Optimal Interconnection Trees in the Plane","author":"B Marcus","year":"2015","unstructured":"Marcus, B., Martin, Z.: Optimal Interconnection Trees in the Plane. Springer, Switzerland (2015)"},{"issue":"1","key":"1163_CR24","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C Monma","year":"1992","unstructured":"Monma, C., Suri, S.: Transitions in geometric minimum spanning trees. Disc. Comput. Geom. 8(1), 265\u2013293 (1992)","journal-title":"Disc. Comput. Geom."},{"issue":"3","key":"1163_CR25","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1002\/net.3230080306","volume":"8","author":"CH Papadimitriou","year":"1978","unstructured":"Papadimitriou, C.H.: The complexity of the capacitated tree problem. Networks 8(3), 217\u2013230 (1978)","journal-title":"Networks"},{"key":"1163_CR26","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"CH Papadimitriou","year":"1998","unstructured":"Papadimitriou, C.H., Steiglitz, D.K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications Inc., New York (1998)"},{"key":"1163_CR27","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"1163_CR28","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2004","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin (2004)"},{"key":"1163_CR29","doi-asserted-by":"publisher","DOI":"10.1201\/9780203497289","volume-title":"Spanning Trees and Optimization Problems","author":"BY Wu","year":"2004","unstructured":"Wu, B.Y., Chao, K.M.: Spanning Trees and Optimization Problems. Chapman & Hall\/CRC, New York (2004)"},{"key":"1163_CR30","unstructured":"Yue, M.Y.: Minimum Network: Steiner Tree Problem (in Chinese). Shanghai Science and Technology Press (2006)"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-022-01163-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-022-01163-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-022-01163-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T06:11:50Z","timestamp":1666246310000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-022-01163-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,6]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1163"],"URL":"https:\/\/doi.org\/10.1007\/s10898-022-01163-x","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2022,6,6]]},"assertion":[{"value":"30 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}