Hardness of Linear Variants of the Balanced Minimum Evolution Problem
Networks · 21.08.2026
DOI: 10.1002/net.70069 ↗Kurz gefasst
Fachartikel in der Zeitschrift Networks, online erschienen am 21.08.2026. Verfasst von Daniele Catanzaro und 3 weiteren Autor:innen. Die Arbeit nennt 29 Literaturangaben. Gefördert von: Fonds De La Recherche Scientifique - FNRS, Fondation Louvain.
Abstract (Originalsprache)
A cubic tree is a tree with leaves in which every internal vertex has degree exactly 3. Any such tree can be encoded by a Path‐Length Matrix (PLM), that is, an integer matrix whose th entry gives the number of edges in the unique path between leaves and in . The convex hull of all PLMs associated with cubic trees on leaves defines the PLM‐polytope . In this article, we prove that optimizing a linear function over the PLM‐polytope is strongly ‐hard. This result is motivated by the balanced minimum evolution problem, a highly nonlinear ‐hard network design problem arising in computational biology, whose underlying combinatorial structure is captured by the PLM‐polytope.
Förderung
- Fonds De La Recherche Scientifique - FNRS
- Fondation Louvain
Zitieren
APA
Catanzaro, D., Joret, G., Pierre, B., & Pisanu, F. (2026). Hardness of Linear Variants of the Balanced Minimum Evolution Problem. Networks. https://doi.org/10.1002/net.70069
Vancouver
Catanzaro D, Joret G, Pierre B, Pisanu F. Hardness of Linear Variants of the Balanced Minimum Evolution Problem. Networks. 2026. doi:10.1002/net.70069
BibTeX
@article{Catanzaro2026,
author = {Catanzaro, Daniele and Joret, Gwenaël and Pierre, Brieuc and Pisanu, Francesco},
title = {Hardness of Linear Variants of the Balanced Minimum Evolution Problem},
journal = {Networks},
year = {2026},
doi = {10.1002/net.70069}
}
EUVIMED