An algorithm for tree-realizability of distance matrices∗
- 1 January 1990
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 34 (3-4) , 171-176
- https://doi.org/10.1080/00207169008803874
Abstract
An algorithm for testing tree realizability of distance matrices is given. It is well-known that if a matrix D has a realization by a tree then such a realization is optimal and unique up to homeomorphism. Our algorithm produces a tree realization or a message that there is no such realization in time O(n 2) where n is the number of points in a finite metric space with the distance matrix D. An O(n 2) algorithm for computing distance matrix for a given tree is also given.Keywords
This publication has 8 references indexed in Scilit:
- A fast algorithm for constructing trees from distance matricesInformation Processing Letters, 1989
- A note on distance matrices with unicyclic graph realizationsDiscrete Mathematics, 1987
- A Note on Optimal and Suboptimal Digraph Realizations of Quasidistance MatricesSIAM Journal on Algebraic Discrete Methods, 1984
- On optimal embeddings of metrics in graphsJournal of Combinatorial Theory, Series B, 1984
- Submatrices of non-tree-realizable distance matricesLinear Algebra and its Applications, 1982
- A note on the tree realizability of a distance matrixJournal of Combinatorial Theory, 1969
- Properties of the distance matrix of a treeQuarterly of Applied Mathematics, 1969
- Distance matrix of a graph and its realizabilityQuarterly of Applied Mathematics, 1965