A fast algorithm for constructing trees from distance matrices

DOI10.1016/0020-0190(89)90216-0zbMath0665.68052OpenAlexW1981192617MaRDI QIDQ1116346

Joseph C. Culberson, Piotr Rudnicki

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90216-0

zbMATH Keywords

random treesdistance matrixtree-realizability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (28)

Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges ⋮ Testing metric properties ⋮ An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree ⋮ Reconstruction of graphs based on random walks ⋮ An algorithm for finding a representation of a subtree distance ⋮ On the longest path algorithm for reconstructing trees from distance matrices ⋮ Tree reconstruction from partial orders ⋮ A branch-price-and-cut algorithm for the minimum evolution problem ⋮ A robust model for finding optimal evolutionary tree ⋮ Vertex-weighted graphs: realizable and unrealizable domains ⋮ A constructive algorithm for realizing a distance matrix ⋮ An algorithm for tree-realizability of distance matrices^∗ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A note on tree realizations of matrices ⋮ The quadratic M-convexity testing problem ⋮ Distance spectra of graphs: a survey ⋮ The minimum evolution problem: Overview and classification ⋮ Composed degree-distance realizations of graphs ⋮ Recognizing and realizing cactus metrics ⋮ Composed degree-distance realizations of graphs ⋮ A Tractable Class of Binary VCSPs via M-Convex Intersection ⋮ An Algorithm for Finding a Representation of a Subtree Distance ⋮ Trees related to realizations of distance matrices ⋮ Tomography on Finite Graphs ⋮ Distance realization problems with applications to internet tomography ⋮ Relaxed and approximate graph realizations ⋮ Recognizing treelike \(k\)-dissimilarities

Cites Work

• Submatrices of non-tree-realizable distance matrices
• The distance matrix of a graph and its tree realization
• An Optimal Diagonal Tree Code
• Distance matrix of a graph and its realizability
• Properties of the distance matrix of a tree
• Unnamed Item
• Unnamed Item

This page was built for publication: A fast algorithm for constructing trees from distance matrices