{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T11:23:12Z","timestamp":1777548192780,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T00:00:00Z","timestamp":1737590400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T00:00:00Z","timestamp":1737590400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Slovak Technical University"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper. Res. Forum"],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In this paper, we introduce a previously not studied type of Euclidean tree called LED (Leaves of Equal Depth) tree. LED trees can be used, for example, in computational phylogeny, since they are a natural representative of the time evolution of a set of species in a feature space. This work is focused on LED trees that are length minimizers for a given set of leaves and a given isomorphism type. The underlying minimization problem can be seen as a variant of the classical Euclidean Steiner tree problem. Even though it has a convex objective function, it is rather non-trivial, since it has a non-convex feasible set. The main contribution of this paper is that we prove the uniqueness of a stationary point of the length function on the feasible set. Moreover, we prove several geometrical characteristics of the length minimizers that are analogous to the properties of Steiner minimal trees. We also explore some geometrical and topological properties of the feasible set. At the end, to demonstrate the applicability of our theoretical results, we show an example of an application in historical linguistics.<\/jats:p>","DOI":"10.1007\/s43069-025-00416-1","type":"journal-article","created":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T11:05:49Z","timestamp":1737630349000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Length-Minimizing LED Trees"],"prefix":"10.1007","volume":"6","author":[{"given":"Mariana","family":"Sarkociov\u00e1 Reme\u0161\u00edkov\u00e1","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Sarkoci","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M\u00e1ria","family":"Trnovsk\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,23]]},"reference":[{"issue":"5","key":"416_CR1","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1080\/09720529.2015.1032623","volume":"18","author":"S Al-Addasi","year":"2015","unstructured":"Al-Addasi S (2015) D-Levels locally homogeneous graphs. J Discr Math Sci Cryptogr 18(5):663\u2013672. https:\/\/doi.org\/10.1080\/09720529.2015.1032623","journal-title":"J Discr Math Sci Cryptogr"},{"key":"416_CR2","doi-asserted-by":"crossref","unstructured":"Bouckaert R, Lemey P, Dunn M, Greenhill SJ, Alekseyenko AV, Drummond AJ, Gray RD, Suchard MA, Atkinson QD (2012) Mapping the origins and expansion of the Indo-European language family. Science 337(6097):957\u2013960. https:\/\/www.science.org\/doi\/10.1126\/science.1219669","DOI":"10.1126\/science.1219669"},{"key":"416_CR3","doi-asserted-by":"crossref","unstructured":"Boyd SP, Vandenberghe L (2004) Convex optimization. Cambridge university press","DOI":"10.1017\/CBO9780511804441"},{"key":"416_CR4","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1002\/net.20279","volume":"53","author":"M Brazil","year":"2008","unstructured":"Brazil M, Thomas DA, Nielsen BK, Winter P, Wulff-Nilsen C, Zachariasen M (2008) A novel approach to phylogenetic trees: d-Dimensional geometric Steiner trees. Networks 53:104\u2013111. https:\/\/doi.org\/10.1002\/net.20279","journal-title":"Networks"},{"key":"416_CR5","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 et al (2014) On the history of the Euclidean Steiner tree problem. Arch Hist Exact Sci 68:327\u2013354. https:\/\/doi.org\/10.1007\/s00407-013-0127-z","journal-title":"Arch Hist Exact Sci"},{"key":"416_CR6","unstructured":"Buckley F, Lewinter M (1988) Minimal graph embeddings, eccentric vertices and the peripherian. In: Proc fifth carribean conference on combinatorics and computing, pp 72\u201384. University of the West Indies"},{"issue":"1","key":"416_CR7","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1353\/lan.2015.0005","volume":"91","author":"W Chang","year":"2015","unstructured":"Chang W, Hall D, Cathcart Ch, Garrett A (2015) Ancestry-constrained phylogenetic analysis supports the Indo-European steppe hypothesis. Language 91(1):194\u2013244. https:\/\/doi.org\/10.1353\/lan.2015.0005","journal-title":"Language"},{"key":"416_CR8","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1038\/nature09923","volume":"473","author":"M Dunn","year":"2011","unstructured":"Dunn M, Greenhill S, Levinson S et al (2011) Evolved structure of language shows lineage-specific trends in word-order universals. Nature 473:79\u201382. https:\/\/doi.org\/10.1038\/nature09923","journal-title":"Nature"},{"key":"416_CR9","doi-asserted-by":"crossref","unstructured":"Dyen I, Kruskal JB, Black P (1992) An Indoeuropean classification: a lexicostatistical experiment. Trans Am Philos Soc 82(5):iii-132","DOI":"10.2307\/1006517"},{"key":"416_CR10","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.dam.2019.03.015","volume":"308","author":"M Fampa","year":"2022","unstructured":"Fampa M (2022) Insight into the computation of Steiner minimal trees in Euclidean space of general dimension. Discr Appl Math 308:4\u201319. https:\/\/doi.org\/10.1016\/j.dam.2019.03.015","journal-title":"Discr Appl Math"},{"key":"416_CR11","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1038\/nature02029","volume":"426","author":"R Gray","year":"2003","unstructured":"Gray R, Atkinson Q (2003) Language-tree divergence times support the Anatolian theory of Indo-European origin. Nature 426:435\u2013439. https:\/\/doi.org\/10.1038\/nature02029","journal-title":"Nature"},{"issue":"3","key":"416_CR12","doi-asserted-by":"publisher","first-page":"231","DOI":"10.21136\/MB.1997.126153","volume":"122","author":"F Gliviak","year":"1997","unstructured":"Gliviak F (1997) Two classes of graphs related to extremal eccentricities. Math Bohem 122(3):231\u2013241","journal-title":"Math Bohem"},{"key":"416_CR13","first-page":"275","volume":"9","author":"F Gliviak","year":"1994","unstructured":"Gliviak F, Knor M, Soltes L (1994) On radially maximal graphs. Australas J Comb 9:275\u2013284","journal-title":"Australas J Comb"},{"issue":"4","key":"416_CR14","doi-asserted-by":"publisher","first-page":"949","DOI":"10.1515\/ling-2020-0060","volume":"59","author":"AS Kassian","year":"2021","unstructured":"Kassian AS, Zhivlov M, Starostin G, Trofimov AA, Kocharov PA, Kuritsyna A, Saenko MN (2021) Rapid radiation of the inner Indo-European languages: an advanced approach to Indo-European lexicostatistics. Linguistics 59(4):949\u2013979. https:\/\/doi.org\/10.1515\/ling-2020-0060","journal-title":"Linguistics"},{"key":"416_CR15","volume-title":"Stru\u010dn\u00fd etymologick\u00fd slovn\u00edk sloven\u010diny","author":"\u013d Kr\u00e1lik","year":"2015","unstructured":"Kr\u00e1lik \u013d (2015) Stru\u010dn\u00fd etymologick\u00fd slovn\u00edk sloven\u010diny. VEDA, Jazykovedn\u00fd \u00fastav \u013d\u0160 SAV"},{"issue":"9","key":"416_CR16","doi-asserted-by":"publisher","first-page":"e0135820","DOI":"10.1371\/journal.pone.0135820","volume":"10","author":"A Kushniarevich","year":"2015","unstructured":"Kushniarevich A, Utevska O, Chuhryaeva M, Agdzhoyan A, Dibirova K, Uktveryte I et al (2015) Genetic heritage of the Balto-Slavic speaking populations: a synthesis of autosomal. Mitochondrial and y-chromosomal data. PLoS One 10(9):e0135820. https:\/\/doi.org\/10.1371\/journal.pone.0135820","journal-title":"PLoS One"},{"issue":"3","key":"416_CR17","doi-asserted-by":"publisher","first-page":"331","DOI":"10.21136\/MB.2000.126124","volume":"125","author":"P Ky\u0161","year":"2000","unstructured":"Ky\u0161 P (2000) Graphs with the same peripheral and center eccentric vertices. Math Bohem 125(3):331\u2013339","journal-title":"Math Bohem"},{"key":"416_CR18","unstructured":"Machek V (2010) Etymologick\u00fd slovn\u00edk jazyka \u010desk\u00e9ho. Nakladatelstv\u00ed Lidov\u00e9 Noviny"},{"key":"416_CR19","first-page":"185","volume":"2","author":"P Novotn\u00e1","year":"2007","unstructured":"Novotn\u00e1 P, Bla\u017eek V (2007) Glottochronology and its applications to Balto-Slavic languages. Baltistica XLII 2:185\u2013210","journal-title":"Baltistica XLII"},{"key":"416_CR20","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s10898-021-01001-6","volume":"83","author":"H Ouzia","year":"2022","unstructured":"Ouzia H, Maculan N (2022) Mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in $$\\mathbb{R}^d$$. J Glob Optim 83:119\u2013136. https:\/\/doi.org\/10.1007\/s10898-021-01001-6","journal-title":"J Glob Optim"},{"key":"416_CR21","doi-asserted-by":"crossref","unstructured":"Petroni F, Serva M (2008) Language distance and tree reconstruction. Journal of Statistical Mechanics: Theory and Experiment 08:08012\u201308027. https:\/\/iopscience.iop.org\/article\/10.1088\/1742-5468\/2008\/08\/P08012","DOI":"10.1088\/1742-5468\/2008\/08\/P08012"},{"key":"416_CR22","doi-asserted-by":"crossref","unstructured":"Sarkociov\u00e1 Reme\u0161\u00edkov\u00e1, M., Sarkoci, P., Trnovsk\u00e1, M (2024) Length-minimizing LED trees. https:\/\/doi.org\/10.48550\/arXiv.2408.11385","DOI":"10.1007\/s43069-025-00416-1"},{"key":"416_CR23","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF01758756","volume":"7","author":"WD Smith","year":"1992","unstructured":"Smith WD (1992) How to find Steiner minimal trees in Euclidean $$d$$-space. Algorithmica 7:137\u2013177. https:\/\/doi.org\/10.1007\/BF01758756","journal-title":"Algorithmica"},{"issue":"1","key":"416_CR24","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1137\/0221013","volume":"21","author":"TL Snyder","year":"1992","unstructured":"Snyder TL (1992) On the exact location of Steiner points in general dimension. SIAM J Comput 21(1):163\u2013180. https:\/\/doi.org\/10.1137\/0221013","journal-title":"SIAM J Comput"},{"key":"416_CR25","first-page":"452","volume":"96","author":"M Swadesh","year":"1952","unstructured":"Swadesh M (1952) Lexicostatistic dating of prehistoric ethnic contacts. Proc Am Philos Soc 96:452\u2013463","journal-title":"Proc Am Philos Soc"},{"key":"416_CR26","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1086\/464321","volume":"21","author":"M Swadesh","year":"1955","unstructured":"Swadesh M (1955) Towards greater accuracy in lexicostatistic dating. Int J Am Ling 21:121\u2013137","journal-title":"Int J Am Ling"},{"key":"416_CR27","doi-asserted-by":"crossref","unstructured":"Weng JF, Mareels I, Thomas DA (2012) Probability Steiner trees and maximum parsimony in phylogenetic analysis. J Math Biol 64(7):1225\u20131251. https:\/\/link.springer.com\/article\/10.1007\/s00285-011-0442-4","DOI":"10.1007\/s00285-011-0442-4"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-025-00416-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-025-00416-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-025-00416-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T11:18:02Z","timestamp":1743333482000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-025-00416-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,23]]},"references-count":27,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["416"],"URL":"https:\/\/doi.org\/10.1007\/s43069-025-00416-1","relation":{},"ISSN":["2662-2556"],"issn-type":[{"value":"2662-2556","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,23]]},"assertion":[{"value":"25 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2025","order":3,"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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"20"}}