Print Email Facebook Twitter Recognizing and realizing cactus metrics Title Recognizing and realizing cactus metrics Author Hayamizu, Momoko (Institute of Statistical Mathematics; Japan Science and Technology Agency) Huber, Katharina T. (University of East Anglia) Moulton, Vincent (University of East Anglia) Murakami, Yukihiro (TU Delft Discrete Mathematics and Optimization) Date 2020-05-01 Abstract The problem of realizing finite metric spaces in terms of weighted graphs has many applications. For example, the mathematical and computational properties of metrics that can be realized by trees have been well-studied and such research has laid the foundation of the reconstruction of phylogenetic trees from evolutionary distances. However, as trees may be too restrictive to accurately represent real-world data or phenomena, it is important to understand the relationship between more general graphs and distances. In this paper, we introduce a new type of metric called a cactus metric, that is, a metric that can be realized by a cactus graph. We show that, just as with tree metrics, a cactus metric has a unique optimal realization. In addition, we describe an algorithm that can recognize whether or not a metric is a cactus metric and, if so, compute its optimal realization in O(n3) time, where n is the number of points in the space. Subject AlgorithmsCactus metricMetric realizationOptimal realizationPhylogenetic network To reference this document use: http://resolver.tudelft.nl/uuid:50bd965d-e53e-4f0e-a1e5-dba01e9e620c DOI https://doi.org/10.1016/j.ipl.2020.105916 ISSN 0020-0190 Source Information Processing Letters, 157 Part of collection Institutional Repository Document type journal article Rights © 2020 Momoko Hayamizu, Katharina T. Huber, Vincent Moulton, Yukihiro Murakami Files PDF 1_s2.0_S002001902030003X_main.pdf 357.08 KB Close viewer /islandora/object/uuid:50bd965d-e53e-4f0e-a1e5-dba01e9e620c/datastream/OBJ/view