Length-Minimizing LED Trees

Mariana Sarkociová Remešíková (), Peter Sarkoci () and Maria Trnovska
Additional contact information
Mariana Sarkociová Remešíková: Slovak University of Technology in Bratislava
Peter Sarkoci: Slovak University of Technology in Bratislava

SN Operations Research Forum, 2025, vol. 6, issue 1, 1-38

Abstract: Abstract 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.

Keywords: LED tree; Euclidean tree; Steiner tree; Euclidean graph; Computational phylogeny; Phylogenetic tree; Length-minimizing tree; Language evolution; 05C05; 05C90; 00A69; 90C26; 49K99 (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-025-00416-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:6:y:2025:i:1:d:10.1007_s43069-025-00416-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-025-00416-1

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().