{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:38Z","timestamp":1740122378955,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,8,26]],"date-time":"2021-08-26T00:00:00Z","timestamp":1629936000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,26]],"date-time":"2021-08-26T00:00:00Z","timestamp":1629936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11861075"],"award-info":[{"award-number":["11861075"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100013047","name":"Cultivating Plan Program for the Leader in Science and Technology of Yunnan Province","doi-asserted-by":"publisher","award":["2018FY001014"],"award-info":[{"award-number":["2018FY001014"]}],"id":[{"id":"10.13039\/501100013047","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Project for Innovation Team (Cultivation) of Yunnan Province"},{"name":"Program for Innovative Research Team (in Science and Technology) in Universities of Yunnan Province","award":["C176240111009"],"award-info":[{"award-number":["C176240111009"]}]},{"name":"Project of Yunling Scholars Training of Yunnan Province"},{"name":"Project of Doctorial Fellow Award of Yunnan Province","award":["2018010514"],"award-info":[{"award-number":["2018010514"]}]},{"DOI":"10.13039\/501100001809","name":"the national natural science foundation of china","doi-asserted-by":"crossref","award":["11461081"],"award-info":[{"award-number":["11461081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s10878-021-00796-0","type":"journal-article","created":{"date-parts":[[2021,8,26]],"date-time":"2021-08-26T19:02:28Z","timestamp":1630004548000},"page":"2832-2852","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["1-line minimum rectilinear steiner trees and related problems"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1508-1440","authenticated-orcid":false,"given":"Jianping","family":"Li","sequence":"first","affiliation":[]},{"given":"Junran","family":"Lichen","sequence":"additional","affiliation":[]},{"given":"Wencheng","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Jean","family":"Yeh","sequence":"additional","affiliation":[]},{"given":"YeongNan","family":"Yeh","sequence":"additional","affiliation":[]},{"given":"Xingxing","family":"Yu","sequence":"additional","affiliation":[]},{"given":"Yujie","family":"Zheng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,26]]},"reference":[{"issue":"1\u20132","key":"796_CR1","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s00453-011-9540-3","volume":"63","author":"A Aazami","year":"2012","unstructured":"Aazami A, Cheriyan J, Jampani KR (2012) Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs. Algorithmica 63(1\u20132):425\u2013456","journal-title":"Algorithmica"},{"issue":"5","key":"796_CR2","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM 45(5):753\u2013782","journal-title":"J ACM"},{"key":"796_CR3","unstructured":"Baratz A (1983) Algorithms for integrated circuit signal routing. PhD thesis, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge"},{"key":"796_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational geometry: algorithms and applications","author":"M Berg","year":"2008","unstructured":"Berg M, Cheong O, Kreveld M, Overmars M (2008) Computational geometry: algorithms and applications. Springer, New York"},{"issue":"4","key":"796_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M Bern","year":"1989","unstructured":"Bern M, Plassmann P (1989) The Steiner problem with edge lengths 1 and 2. Inf Process Lett 32(4):171\u2013176","journal-title":"Inf Process Lett"},{"key":"796_CR6","doi-asserted-by":"crossref","unstructured":"Byrka J, Grandoni F, Rothvo\u00df T, Sanit\u00e0 L (2010) An improved LP-based approximation for Steiner tree. In: Proceedings of the 2010 ACM International Symposium on Theory of Computing, pp 583\u2013592","DOI":"10.1145\/1806689.1806769"},{"issue":"9","key":"796_CR7","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1016\/S0305-0548(99)00061-1","volume":"27","author":"G Chen","year":"2000","unstructured":"Chen G, Zhang G (2000) A constrained minimum spanning tree problem. Comput Oper Res 27(9):867\u2013875","journal-title":"Comput Oper Res"},{"key":"796_CR8","doi-asserted-by":"crossref","unstructured":"Cheng X, Du D (2001) Steiner Trees in Industry. Combinatorial Optimization 11, Springer US","DOI":"10.1007\/978-1-4613-0255-1"},{"issue":"1","key":"796_CR9","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1111\/j.1749-6632.1985.tb14564.x","volume":"440","author":"F Chung","year":"1982","unstructured":"Chung F, Graham R (1982) A new bound for Euclidean Steiner minimal trees. Ann New York Acad Sci 440(1):328\u2013346","journal-title":"Ann New York Acad Sci"},{"key":"796_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6585-4","volume-title":"Steiner Minimal Trees","author":"D Cieslik","year":"1998","unstructured":"Cieslik D (1998) Steiner Minimal Trees. Kluwer Academic Publishers, Amsterdam"},{"issue":"4","key":"796_CR11","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M Garey","year":"1977","unstructured":"Garey M, Graham R, Johnson D (1977) The complexity of computing Steiner minimal trees. SIAM J Appl Math 32(4):835\u2013859","journal-title":"SIAM J Appl Math"},{"issue":"1","key":"796_CR12","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/0196-6774(87)90032-0","volume":"8","author":"G Georgakopoulos","year":"1987","unstructured":"Georgakopoulos G, Papadimitriou CH (1987) The 1-Steiner tree problem. J Alg 8(1):122\u2013130","journal-title":"J Alg"},{"issue":"1","key":"796_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"EN Gilbert","year":"1968","unstructured":"Gilbert EN, Pollak HO (1968) Steiner minimal trees. SIAM J Appl Math 16(1):1\u201329","journal-title":"SIAM J Appl Math"},{"issue":"1","key":"796_CR14","first-page":"123","volume":"18","author":"J Holby","year":"2017","unstructured":"Holby J (2017) Variations on the Euclidean Steiner tree problem and algorithms. Rose-Hulman Undergrad Math J 18(1):123\u2013155","journal-title":"Rose-Hulman Undergrad Math J"},{"issue":"1","key":"796_CR15","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"FK Hwang","year":"1976","unstructured":"Hwang FK (1976) On Steiner minimal trees with rectilinear distance. SIAM J Appl Math 30(1):104\u2013114","journal-title":"SIAM J Appl Math"},{"issue":"2","key":"796_CR16","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/322123.322124","volume":"26","author":"FK Hwang","year":"1979","unstructured":"Hwang FK (1979) An $$O ( n \\log n )$$ algorithm for rectilinear minimal spanning trees. J ACM 26(2):177\u2013182","journal-title":"J ACM"},{"issue":"1","key":"796_CR17","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/net.3230220105","volume":"22","author":"FK Hwang","year":"1992","unstructured":"Hwang FK, Richards DS (1992) Steiner tree problems. Networks 22(1):55\u201389","journal-title":"Networks"},{"issue":"3","key":"796_CR18","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M Imase","year":"1991","unstructured":"Imase M, Waxman BM (1991) Dynamic Steiner tree problem. SIAM J Dis Math 4(3):369\u2013384","journal-title":"SIAM J Dis Math"},{"issue":"4","key":"796_CR19","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Johnson","year":"1977","unstructured":"Johnson MR, Garey 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":"796_CR20","volume-title":"Combinatorial optimization: theory and algorithms","author":"B Korte","year":"2008","unstructured":"Korte B, Vygen J (2008) Combinatorial optimization: theory and algorithms. Springer, Berlin"},{"issue":"1","key":"796_CR21","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proceed Am Math Soc 7(1):48\u201350","journal-title":"Proceed Am Math Soc"},{"issue":"2","key":"796_CR22","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1007\/s10878-019-00492-0","volume":"39","author":"JP Li","year":"2020","unstructured":"Li JP, Liu SD, Lichen JR, Wang WC, Zheng YJ (2020) Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem. J Comb Opt 39(2):492\u2013508","journal-title":"J Comb Opt"},{"issue":"1","key":"796_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/trsc.14.1.1","volume":"14","author":"JG Morris","year":"1980","unstructured":"Morris JG, Norback JP (1980) A simple approach to linear facility location. Transp Sci 14(1):1\u20138","journal-title":"Transp Sci"},{"issue":"6","key":"796_CR24","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36(6):1389\u20131401","journal-title":"Bell Syst Tech J"},{"issue":"1\u20134","key":"796_CR25","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01553886","volume":"4","author":"DS Richards","year":"1989","unstructured":"Richards DS (1989) Fast heuristic algorithms for rectilinear Steiner trees. Algorithmica 4(1\u20134):191\u2013207","journal-title":"Algorithmica"},{"issue":"4","key":"796_CR26","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0167-6377(92)90053-6","volume":"12","author":"JS Salowe","year":"1992","unstructured":"Salowe JS (1992) A simple proof of the planar rectilinear Steiner ratio. Oper Res Lett 12(4):271\u2013274","journal-title":"Oper Res Lett"},{"key":"796_CR27","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, Berlin"},{"key":"796_CR28","doi-asserted-by":"crossref","unstructured":"Shamos MI, Hoey D (1975) Closest-point problems. In: The 16th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, pp 151\u2013162","DOI":"10.1109\/SFCS.1975.8"},{"key":"796_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press, Cambridge"},{"issue":"4","key":"796_CR30","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"AC Yao","year":"1982","unstructured":"Yao AC (1982) On constructing minimum spanning trees in $$k$$-dimensional spaces and related problems. SIAM J Comput 11(4):721\u2013736","journal-title":"SIAM J Comput"},{"issue":"5","key":"796_CR31","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0020-0190(01)00232-0","volume":"81","author":"H Zhou","year":"2002","unstructured":"Zhou H, Shenoy N, Nicholls W (2002) Efficient minimum spanning tree construction without Delaynay triangulation. Inf Proc Lett 81(5):271\u2013276","journal-title":"Inf Proc Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00796-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00796-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00796-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,7]],"date-time":"2023-11-07T22:22:06Z","timestamp":1699395726000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00796-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,26]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["796"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00796-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,8,26]]},"assertion":[{"value":"13 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}