A fast algorithm for constructing trees from distance matrices
type: Item
instance of: scholarly article
title: A fast algorithm for constructing trees from distance matrices
zbMATH Open document ID: 0665.68052
DOI: 10.1016/0020-0190(89)90216-0
author: J. Culberson
author: Piotr Rudnicki
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 4088946
zbMATH Keywords: random trees
zbMATH Keywords: tree-realizability
zbMATH Keywords: distance matrix
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90216-0
OpenAlex ID: W1981192617
cites work: Properties of the distance matrix of a tree
cites work: An Optimal Diagonal Tree Code
cites work: Distance matrix of a graph and its realizability
cites work: Q3680834
cites work: The distance matrix of a graph and its tree realization
cites work: Submatrices of non-tree-realizable distance matrices
cites work: Q5530466
description: scientific article; zbMATH DE number 4088946