Recognizing and realizing cactus metrics

DOI10.1016/j.ipl.2020.105916zbMath1447.05186arXiv1908.01524OpenAlexW2999125311WikidataQ126347120 ScholiaQ126347120MaRDI QIDQ2296277

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

Publication date: 18 February 2020

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

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

zbMATH Keywords

algorithmsphylogenetic networkoptimal realizationcactus metricmetric realization

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• An algorithm for computing cutpoints in finite metric spaces
• The metric cutpoint partition problem
• On optimal embeddings of metrics in graphs
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• On optimal realizations of finite metric spaces by graphs
• A fast algorithm for constructing trees from distance matrices
• A note on distance matrices with unicyclic graph realizations
• Submatrices of non-tree-realizable distance matrices
• An algorithm for tree-realizability of distance matrices^∗
• The Complexity of Metric Realization
• Recognition of Tree Metrics
• Distance matrix of a graph and its realizability