{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T03:31:56Z","timestamp":1773199916346,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,9,21]],"date-time":"2021-09-21T00:00:00Z","timestamp":1632182400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,9,21]],"date-time":"2021-09-21T00:00:00Z","timestamp":1632182400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"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-00808-z","type":"journal-article","created":{"date-parts":[[2021,9,21]],"date-time":"2021-09-21T12:27:59Z","timestamp":1632227279000},"page":"2893-2918","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the restricted k-Steiner tree problem"],"prefix":"10.1007","volume":"44","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[]},{"given":"Anthony","family":"D\u2019Angelo","sequence":"additional","affiliation":[]},{"given":"Stephane","family":"Durocher","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,21]]},"reference":[{"issue":"4","key":"808_CR1","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1007\/s00453-011-9553-y","volume":"61","author":"SW Bae","year":"2011","unstructured":"Bae SW, Choi S, Lee C, Tanigawa S (2011) Exact algorithms for the bottleneck Steiner tree problem. Algorithmica 61(4):924\u2013948","journal-title":"Algorithmica"},{"issue":"16","key":"808_CR2","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1016\/j.ipl.2010.05.014","volume":"110","author":"SW Bae","year":"2010","unstructured":"Bae SW, Lee C, Choi S (2010) On exact solutions to the Euclidean bottleneck Steiner tree problem. Inf Process Lett 110(16):672\u2013678","journal-title":"Inf Process Lett"},{"key":"808_CR3","doi-asserted-by":"crossref","unstructured":"Bender MA, Farach-Colton M (2000) The LCA problem revisited. In: LATIN, Lecture Notes in Computer Science, vol. 1776, pp. 88\u201394. Springer","DOI":"10.1007\/10719839_9"},{"key":"808_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational geometry: algorithms and applications","author":"M de Berg","year":"2008","unstructured":"de Berg M, Cheong O, van Kreveld MJ, Overmars MH (2008) Computational geometry: algorithms and applications, 3rd edn. Springer, New York","edition":"3"},{"issue":"2&3","key":"808_CR5","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF01758760","volume":"7","author":"RS Booth","year":"1992","unstructured":"Booth RS, Weng JF (1992) Steiner minimal trees for a class of zigzag lines. Algorithmica 7(2 & 3):231\u2013246","journal-title":"Algorithmica"},{"key":"808_CR6","doi-asserted-by":"crossref","unstructured":"Bose P, D\u2019Angelo A, Durocher S (2020) On the restricted 1-Steiner tree problem. In: COCOON, Lecture Notes in Computer Science, vol. 12273, pp. 448\u2013459. Springer","DOI":"10.1007\/978-3-030-58150-3_36"},{"issue":"3","key":"808_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.comgeo.2004.04.003","volume":"29","author":"P Bose","year":"2004","unstructured":"Bose P, Maheshwari A, Narasimhan G, Smid MHM, Zeh N (2004) Approximating geometric bottleneck shortest paths. Comput Geom 29(3):233\u2013249","journal-title":"Comput Geom"},{"issue":"1","key":"808_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1006\/jcta.1996.0004","volume":"73","author":"M Brazil","year":"1996","unstructured":"Brazil M, Cole T, Rubinstein JH, Thomas DA, Weng JF, Wormald NC (1996) Minimal Steiner trees for $$2^{{ k}} \\times 2^{{ k}}$$ square lattices. J Comb Theory Ser A 73(1):91\u2013110","journal-title":"J Comb Theory Ser A"},{"issue":"3","key":"808_CR9","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00407-013-0127-z","volume":"68","author":"M Brazil","year":"2014","unstructured":"Brazil M, Graham RL, Thomas DA, Zachariasen M (2014) On the history of the Euclidean Steiner tree problem. Arch. History Exact Sci. 68(3):327\u2013354","journal-title":"Arch. History Exact Sci."},{"issue":"1","key":"808_CR10","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/s00453-013-9780-5","volume":"71","author":"M Brazil","year":"2015","unstructured":"Brazil M, Ras CJ, Swanepoel KJ, Thomas DA (2015) Generalised k-Steiner tree problems in normed planes. Algorithmica 71(1):66\u201386","journal-title":"Algorithmica"},{"issue":"1","key":"808_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/jcta.1996.2752","volume":"78","author":"M Brazil","year":"1997","unstructured":"Brazil M, Rubinstein JH, Thomas DA, Weng JF, Wormald NC (1997a) Full minimal Steiner trees on lattice sets. J Comb Theory Ser A 78(1):51\u201391","journal-title":"J Comb Theory Ser A"},{"issue":"2","key":"808_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1006\/jcta.1996.2751","volume":"79","author":"M Brazil","year":"1997","unstructured":"Brazil M, Rubinstein JH, Thomas DA, Weng JF, Wormald NC (1997b) Minimal Steiner trees for rectangular arrays of lattice points. J Comb Theory Ser A 79(2):181\u2013208","journal-title":"J Comb Theory Ser A"},{"issue":"2","key":"808_CR13","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1023\/A:1009846620554","volume":"4","author":"M Brazil","year":"2000","unstructured":"Brazil M, Thomas DA, Weng JF (2000) On the complexity of the Steiner problem. J Comb Optim 4(2):187\u2013195","journal-title":"J Comb Optim"},{"key":"808_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-13915-9","volume-title":"Optimal interconnection trees in the plane: theory, algorithms and applications","author":"M Brazil","year":"2015","unstructured":"Brazil M, Zachariasen M (2015) Optimal interconnection trees in the plane: theory, algorithms and applications, vol 29. Springer, New York"},{"issue":"5","key":"808_CR15","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0020-0190(90)90054-2","volume":"35","author":"M Chang","year":"1990","unstructured":"Chang M, Huang N, Tang CY (1990) An optimal algorithm for constructing oriented Voronoi diagrams and geographic neighborhood graphs. Inf Process Lett 35(5):255\u2013260","journal-title":"Inf Process Lett"},{"issue":"1","key":"808_CR16","first-page":"76","volume":"25","author":"B Chazelle","year":"1985","unstructured":"Chazelle B, Guibas LJ, Lee DT (1985) The power of geometric duality. BIT Comput Sci Sect 25(1):76\u201390","journal-title":"BIT Comput Sci Sect"},{"issue":"9","key":"808_CR17","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"},{"issue":"4","key":"808_CR18","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1137\/0205051","volume":"5","author":"DR Cheriton","year":"1976","unstructured":"Cheriton DR, Tarjan RE (1976) Finding minimum spanning trees. SIAM J Comput 5(4):724\u2013742","journal-title":"SIAM J Comput"},{"key":"808_CR19","doi-asserted-by":"crossref","unstructured":"Chew LP, Drysdale III RL (1985) Voronoi diagrams based on convex distance functions. In: Symposium on Computational Geometry, pp. 235\u2013244. ACM","DOI":"10.1145\/323233.323264"},{"key":"808_CR20","doi-asserted-by":"crossref","unstructured":"Chung FRK, Graham RL (1978) Steiner trees for ladders. Annal Discrete Math 2:173\u2013200","DOI":"10.1016\/S0167-5060(08)70332-7"},{"issue":"1","key":"808_CR21","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 FRK, Graham RL (1985) A new bound for Euclidean Steiner minimal trees. Annal New York Acad Sci 440(1):328\u2013346","journal-title":"Annal New York Acad Sci"},{"issue":"1","key":"808_CR22","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1090\/S0002-9947-1983-0697066-5","volume":"278","author":"D Du","year":"1983","unstructured":"Du D, Hwang F, Weng J (1983) Steiner minimal trees on zig-zag lines. Trans Am Math Soc 278(1):149\u2013156","journal-title":"Trans Am Math Soc"},{"key":"808_CR23","doi-asserted-by":"crossref","unstructured":"Edelsbrunner H, O\u2019Rourke J, Seidel R (1986) Constructing arrangements of lines and hyperplanes with applications. SIAM J Comput 15(2):341\u2013363","DOI":"10.1137\/0215024"},{"issue":"2","key":"808_CR24","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/0222031","volume":"22","author":"H Edelsbrunner","year":"1993","unstructured":"Edelsbrunner H, Seidel R, Sharir M (1993) On the zone theorem for hyperplane arrangements. SIAM J Comput 22(2):418\u2013429","journal-title":"SIAM J Comput"},{"issue":"4","key":"808_CR25","doi-asserted-by":"publisher","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"},{"key":"808_CR26","doi-asserted-by":"crossref","unstructured":"Georgakopoulos GK, Papadimitriou CH (1987) The 1-Steiner tree problem. J Algorithms 8(1):122\u2013130","DOI":"10.1016\/0196-6774(87)90032-0"},{"issue":"1","key":"808_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"E Gilbert","year":"1968","unstructured":"Gilbert E, Pollak H (1968) Steiner minimal trees. SIAM J Appl Math 16(1):1\u201329","journal-title":"SIAM J Appl Math"},{"key":"808_CR28","unstructured":"Goodman JE, O\u2019Rourke J, T\u00f3th CD (eds.) (2017) Handbook of Discrete and Computational Geometry, Third Edition. Chapman and Hall\/CRC Press"},{"issue":"2","key":"808_CR29","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel D, Tarjan RE (1984) Fast algorithms for finding nearest common ancestors. SIAM J Comput 13(2):338\u2013355","journal-title":"SIAM J Comput"},{"issue":"1","key":"808_CR30","first-page":"7","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):7","journal-title":"Rose-Hulman Undergrad Math J"},{"issue":"2","key":"808_CR31","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1007\/s10878-019-00492-0","volume":"39","author":"J Li","year":"2020","unstructured":"Li J, Liu S, Lichen J, Wang W, Zheng Y (2020) Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem. J Comb Optim 39(2):492\u2013508","journal-title":"J Comb Optim"},{"key":"808_CR32","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"CL Monma","year":"1992","unstructured":"Monma CL, Suri S (1992) Transitions in geometric minimum spanning trees. Discret Comput Geom 8:265\u2013293","journal-title":"Discret Comput Geom"},{"key":"808_CR33","doi-asserted-by":"crossref","unstructured":"Preparata FP, Shamos MI (1985) Computational Geometry - An Introduction. Texts and Monographs in Computer Science. Springer","DOI":"10.1007\/978-1-4612-1098-6"},{"issue":"6","key":"808_CR34","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1002\/net.3230220604","volume":"22","author":"JH Rubinstein","year":"1992","unstructured":"Rubinstein JH, Thomas DA, Weng JF (1992) Degree-five Steiner points cannot reduce network costs for planar sets. Networks 22(6):531\u2013537","journal-title":"Networks"},{"issue":"1","key":"808_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480192241190","volume":"10","author":"JH Rubinstein","year":"1997","unstructured":"Rubinstein JH, Thomas DA, Wormald NC (1997) Steiner trees for terminals constrained to curves. SIAM J Discret Math 10(1):1\u201317","journal-title":"SIAM J Discret Math"},{"issue":"6","key":"808_CR36","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B Schieber","year":"1988","unstructured":"Schieber B, Vishkin U (1988) On finding lowest common ancestors: Simplification and parallelization. SIAM J Comput 17(6):1253\u20131262","journal-title":"SIAM J Comput"},{"issue":"5","key":"808_CR37","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1111\/cgf.12437","volume":"33","author":"J Vanek","year":"2014","unstructured":"Vanek J, Galicia JAG, Benes B (2014) Clever support: efficient support structure generation for digital fabrication. Comput Graph Forum 33(5):117\u2013125","journal-title":"Comput Graph Forum"},{"issue":"2","key":"808_CR38","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(93)90092-3","volume":"47","author":"P Winter","year":"1993","unstructured":"Winter P (1993) Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs. Discrete Appl. Math. 47(2):187\u2013206","journal-title":"Discrete Appl. Math."},{"key":"808_CR39","unstructured":"Winter P (1995a) Euclidean Steiner minimum trees for 3 terminals in a simple polygon. In: Proceedings of the Seventh Canadian Conference on Computational Geometry, Univ. Laval, Quebec, Canada, pp. 247\u2013255"},{"key":"808_CR40","unstructured":"Winter P (1995b) Steiner minimum trees in simple polygons. DIMACS Technical Report 95\u201343"},{"issue":"1\u20132","key":"808_CR41","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0166-218X(01)00256-6","volume":"118","author":"P Winter","year":"2002","unstructured":"Winter P, Zachariasen M, Nielsen J (2002) Short trees in polygons. Discret Appl Math 118(1\u20132):55\u201372","journal-title":"Discret Appl Math"},{"key":"808_CR42","doi-asserted-by":"crossref","unstructured":"Zachariasen M, Winter P (1999) Obstacle-avoiding Euclidean Steiner trees in the plane: An exact algorithm. In: ALENEX, Lecture Notes in Computer Science, vol. 1619, pp. 282\u2013295. Springer","DOI":"10.1007\/3-540-48518-X_17"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00808-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00808-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00808-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,9]],"date-time":"2023-11-09T04:23:06Z","timestamp":1699503786000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00808-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,21]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["808"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00808-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,21]]},"assertion":[{"value":"27 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}