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 wellstudied 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 realworld 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(n^3)$ time, where $n$ is the number of points in the space.
Original language  English 

Article number  105916 
Number of pages  5 
Journal  Information Processing Letters 
Volume  157 
Early online date  16 Jan 2020 
DOIs  
Publication status  Published  1 May 2020 
Keywords
 ALGORITHM
 Algorithms
 Cactus metric
 DISTANCE MATRICES
 Metric realization
 Optimal realization
 Phylogenetic network
 SPACES
 TREES
Profiles

Katharina Huber
 School of Computing Sciences  Associate Professor
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research

Vincent Moulton
 School of Computing Sciences  Professor in Computational Biology
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research