Recognizing and realizing cactus metrics

DOI10.1016/J.IPL.2020.105916MaRDI QIDQ2296277zbMATH OpenOpenAlexWikidataFDO

Authors Momoko Hayamizu, Katharina T. Huber, Yukihiro Murakami, Vincent Moulton

Publication date 18 February 2020

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1908.01524

zbMATH Keywords

algorithmscactus metricmetric realizationoptimal realizationphylogenetic network

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Signed and weighted graphs (05C22) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15)

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

Recommendations

• On optimal realizations of finite metric spaces by graphs
• scientific article; zbMATH DE number 975398
• Concerning the relationship between realizations and tight spans of finite metrics
• Searching for realizations of finite metric spaces in tight spans
• Injective optimal realizations of finite metric spaces

Cites work

• A fast algorithm for constructing trees from distance matrices
• A note on distance matrices with unicyclic graph realizations
• An algorithm for computing cutpoints in finite metric spaces
• An algorithm for tree-realizability of distance matrices^∗
• Distance matrix of a graph and its realizability
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 6857397 (Why is no real title available?)
• On optimal embeddings of metrics in graphs
• On optimal realizations of finite metric spaces by graphs
• Recognition of Tree Metrics
• Submatrices of non-tree-realizable distance matrices
• The Complexity of Metric Realization
• The metric cutpoint partition problem
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces

Cited in

(5)

• Encoding and ordering X-cactuses
• Reconstructibility of unrooted level-k phylogenetic networks from distances
• Determining triangulations and quadrangulations by boundary distances
• Polynomial invariants for cactuses
• The space of equidistant phylogenetic cactuses

This page was built for publication: Recognizing and realizing cactus metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2296277)