IDEAS home Printed from https://ideas.repec.org/a/spr/snopef/v6y2025i1d10.1007_s43069-025-00416-1.html
   My bibliography  Save this article

Length-Minimizing LED Trees

Author

Listed:
  • Mariana Sarkociová Remešíková

    (Slovak University of Technology in Bratislava)

  • Peter Sarkoci

    (Slovak University of Technology in Bratislava)

  • Mária Trnovská

    (Physics and Informatics)

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.

Suggested Citation

  • Mariana Sarkociová Remešíková & Peter Sarkoci & Mária Trnovská, 2025. "Length-Minimizing LED Trees," SN Operations Research Forum, Springer, vol. 6(1), pages 1-38, March.
    • Handle: RePEc:spr:snopef:v:6:y:2025:i:1:d:10.1007_s43069-025-00416-1
    DOI: 10.1007/s43069-025-00416-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s43069-025-00416-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s43069-025-00416-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Michael Dunn & Simon J. Greenhill & Stephen C. Levinson & Russell D. Gray, 2011. "Evolved structure of language shows lineage-specific trends in word-order universals," Nature, Nature, vol. 473(7345), pages 79-82, May.
    2. Hacene Ouzia & Nelson Maculan, 2022. "Mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in $$\mathbb {R}^d$$ R d," Journal of Global Optimization, Springer, vol. 83(1), pages 119-136, May.
    3. Russell D. Gray & Quentin D. Atkinson, 2003. "Language-tree divergence times support the Anatolian theory of Indo-European origin," Nature, Nature, vol. 426(6965), pages 435-439, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Klaus Desmet & Ignacio Ortuño-Ortín & Romain Wacziarg, 2009. "The political economy of ethnolinguistic cleavages," Working Papers 2009-17, Instituto Madrileño de Estudios Avanzados (IMDEA) Ciencias Sociales.
    2. Victor Ginsburgh & Shlomo Weber, 2020. "The Economics of Language," Journal of Economic Literature, American Economic Association, vol. 58(2), pages 348-404, June.
    3. Joseph Flavian Gomes, 2020. "The health costs of ethnic distance: evidence from sub-Saharan Africa," Journal of Economic Growth, Springer, vol. 25(2), pages 195-226, June.
    4. Aparicio Fenoll, Ainoa & Kuehn, Zoë, 2016. "Education Policies and Migration across European Countries," IZA Discussion Papers 9755, Institute of Labor Economics (IZA).
    5. Ainhoa Aparicio Fenoll & Zoë Kuehn, 2017. "Compulsory Schooling Laws and Migration Across European Countries," Demography, Springer;Population Association of America (PAA), vol. 54(6), pages 2181-2200, December.
    6. Stanisz, Tomasz & Drożdż, Stanisław & Kwapień, Jarosław, 2023. "Universal versus system-specific features of punctuation usage patterns in major Western languages," Chaos, Solitons & Fractals, Elsevier, vol. 168(C).
    7. Desmet, Klaus & Ortuño-Ortín, Ignacio & Wacziarg, Romain, 2012. "The political economy of linguistic cleavages," Journal of Development Economics, Elsevier, vol. 97(2), pages 322-338.
    8. Petroni, Filippo & Serva, Maurizio, 2010. "Measures of lexical distance between languages," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(11), pages 2280-2283.
    9. Ginsburgh, Victor & Weber, Shlomo, 2015. "Linguistic Distances and their Use in Economics," CEPR Discussion Papers 10640, C.E.P.R. Discussion Papers.
    10. Matthew J. Baker, 2021. "Foundations of the Age-Area Hypothesis," Palgrave Communications, Palgrave Macmillan, vol. 8(1), pages 1-17, December.
    11. Simone Pompei & Vittorio Loreto & Francesca Tria, 2011. "On the Accuracy of Language Trees," PLOS ONE, Public Library of Science, vol. 6(6), pages 1-11, June.
    12. Stelios Michalopoulos, 2012. "The Origins of Ethnolinguistic Diversity," American Economic Review, American Economic Association, vol. 102(4), pages 1508-1539, June.
    13. Carl Müller-Crepon & Yannick Pengl & Nils-Christian Bormann, 2022. "Linking Ethnic Data from Africa (LEDA)," Journal of Peace Research, Peace Research Institute Oslo, vol. 59(3), pages 425-435, May.
    14. Takuma Tanaka, 2025. "Mean-reverting self-excitation drives evolution: phylogenetic analysis of a literary genre, waka, with a neural language model," Palgrave Communications, Palgrave Macmillan, vol. 12(1), pages 1-10, December.
    15. Ilja A. Seržant & George Moroz, 2022. "Universal attractors in language evolution provide evidence for the kinds of efficiency pressures involved," Palgrave Communications, Palgrave Macmillan, vol. 9(1), pages 1-9, December.
    16. Stelios Michalopoulos, 2008. "The Origins of Ethnolinguistic Diversity: Theory and Evidence," Discussion Papers Series, Department of Economics, Tufts University 0725, Department of Economics, Tufts University.
    17. Nico Neureiter & Peter Ranacher & Nour Efrat-Kowalsky & Gereon A. Kaiping & Robert Weibel & Paul Widmer & Remco R. Bouckaert, 2022. "Detecting contact in language trees: a Bayesian phylogenetic model with horizontal transfer," Palgrave Communications, Palgrave Macmillan, vol. 9(1), pages 1-14, December.
    18. Victor GINSBURGH & Shlomo WEBER, 2016. "Linguistic distances and ethnolinguistic fractionalization and disenfranchisement indices," LIDAM Reprints CORE 2855, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    19. Aguilar, Elliot & Ghirlanda, Stefano, 2015. "Modeling the genealogy of a cultural trait," Theoretical Population Biology, Elsevier, vol. 101(C), pages 1-8.
    20. Victor Zitian Chen & John Cantwell, 2022. "An evolutionary view of institutional complexity," Journal of Evolutionary Economics, Springer, vol. 32(3), pages 1071-1090, July.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:snopef:v:6:y:2025:i:1:d:10.1007_s43069-025-00416-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.