TY - JOUR

T1 - Recognizing and realizing cactus metrics

AU - Hayamizu, Momoko

AU - Huber, Katharina T.

AU - Moulton, Vincent

AU - Murakami, Yukihiro

PY - 2020/5/1

Y1 - 2020/5/1

N2 - 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.

AB - 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.

KW - Algorithms

KW - Cactus metric

KW - Metric realization

KW - Optimal realization

KW - Phylogenetic network

UR - http://www.scopus.com/inward/record.url?scp=85078448272&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2020.105916

DO - 10.1016/j.ipl.2020.105916

M3 - Article

AN - SCOPUS:85078448272

VL - 157

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

M1 - 105916

ER -