A fast algorithm for constructing trees from distance matrices
From MaRDI portal
We present an algorithm which, given a tree-realizable distance matrix, constructs the tree in optimal \(O(n^ 2)\) time. For trees of bounded degree k, the algorithm runs in O(k n \(log_ k n)\) time, and for random trees it apparently runs in O(n) average time. We show how the algorithm can be used to test tree-realizability of a distance matrix.
Recommendations
- An algorithm for tree-realizability of distance matrices∗
- An optimal algorithm to reconstruct trees from additive distance data
- On the longest path algorithm for reconstructing trees from distance matrices
- A polynomial time algorithm for constructing the refined Buneman tree
- A robust model for finding optimal evolutionary tree
Cites work
- An Optimal Diagonal Tree Code
- Distance matrix of a graph and its realizability
- scientific article; zbMATH DE number 3902655 (Why is no real title available?)
- scientific article; zbMATH DE number 3243264 (Why is no real title available?)
- Properties of the distance matrix of a tree
- Submatrices of non-tree-realizable distance matrices
- The distance matrix of a graph and its tree realization
Cited in
(47)- An optimal algorithm to reconstruct trees from additive distance data
- Melzak algorithm for phylogenetic spaces
- Trees related to realizations of distance matrices
- Distance realization problems with applications to internet tomography
- An algorithm for finding a representation of a subtree distance
- The quadratic M-convexity testing problem
- A polynomial time algorithm for constructing the refined Buneman tree
- Testing metric properties
- A robust model for finding optimal evolutionary tree
- Relaxed and approximate graph realizations
- Vertex-weighted graphs: realizable and unrealizable domains
- Distance spectra of graphs: a survey
- Recognizing and realizing cactus metrics
- Recognizing treelike k-dissimilarities
- The triangles method to build X-trees from incomplete distance matrices
- Provably fast and accurate recovery of evolutionary trees through harmonic greedy triplets
- An algorithm for finding a representation of a subtree distance
- Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges
- An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree
- A branch-price-and-cut algorithm for the minimum evolution problem
- Tomography on Finite Graphs
- An algorithm for tree-realizability of distance matrices∗
- A note on tree realizations of matrices
- Maximal Accurate Forests from Distance Matrices
- scientific article; zbMATH DE number 1222844 (Why is no real title available?)
- A tractable class of binary VCSPs via M-convex intersection
- Parameterized algorithms for zero extension and metric labelling problems
- Tree reconstruction from partial orders
- Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees
- The minimum evolution problem: Overview and classification
- Efficient algorithms for inferring evolutionary trees
- scientific article; zbMATH DE number 7651142 (Why is no real title available?)
- Composed degree-distance realizations of graphs
- Composed degree-distance realizations of graphs
- Generation matrix: an embeddable matrix representation for hierarchical trees
- Graph realization of distance sets
- Exact learning of weighted graphs using composite queries
- Computational complexity of combinatorial distance matrix realisation
- Temporal graph realization from fastest paths
- Constructing tree-child networks from distance matrices
- Realizing temporal transportation trees
- Learning latent tree models with small query complexity
- The tree nearest on average to a given set of trees
- Reconstruction of graphs based on random walks
- On the longest path algorithm for reconstructing trees from distance matrices
- A constructive algorithm for realizing a distance matrix
- Analysis of a modification of Gusfield's recursive algorithm for reconstructing ultrametric trees
This page was built for publication: A fast algorithm for constructing trees from distance matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116346)
