TY - JOUR
T1 - Recognizing and realizing cactus metrics
AU - Hayamizu, Momoko
AU - Huber, Katharina T.
AU - Moulton, Vincent
AU - Murakami, Yukihiro
N1 - Funding Information:
MH is supported by JST PRESTO Grant Number JPMJPR16EB , ISM Cooperative Research Program Grant Number 2019-ISMCRP-2020 , and "Challenging Exploratory Research Projects for the Future" grant from Research Organization of Information and Systems . MH, KH and VM thank the Research Institute for Mathematical Sciences, an International Joint Usage/Research Center located in Kyoto University, for its support. KH and VM thank the London Mathematical Society for their support. KH, VM and YM thank the Netherlands Organisation for Scientific Research (NWO), including Vidi grant 639.072.602 .
Funding Information:
MH is supported by JST PRESTO Grant Number JPMJPR16EB, ISM Cooperative Research Program Grant Number 2019-ISMCRP-2020, and “Challenging Exploratory Research Projects for the Future” grant from Research Organization of Information and Systems. MH, KH and VM thank the Research Institute for Mathematical Sciences, an International Joint Usage/Research Center located in Kyoto University, for its support. KH and VM thank the London Mathematical Society for their support. KH, VM and YM thank the Netherlands Organisation for Scientific Research (NWO), including Vidi grant 639.072.602.
Publisher Copyright:
© 2020 The Authors
PY - 2020/5
Y1 - 2020/5
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
UR - http://www.scopus.com/inward/citedby.url?scp=85078448272&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2020.105916
DO - 10.1016/j.ipl.2020.105916
M3 - Article
AN - SCOPUS:85078448272
SN - 0020-0190
VL - 157
JO - Information Processing Letters
JF - Information Processing Letters
M1 - 105916
ER -