2024/12/04 by Gardiner, Jack, Andrew, Lachlan L. H., Gan, Junhao +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2412.03138
This paper tightens the best known analysis of Hein's 1989 algorithm to infer the topology of a weighted tree based on the lengths of paths between its leaves. It shows that the number of length queries required for a degree-k tree of n leaves is O(n k logk n), which is the lower bound. It also presents a family of trees for which the performance is asymptotically better, and shows that no such family exists for a competing O(n k logk n) algorithm.