Optimal bounds on a tree inference algorithm

作     者：Gardiner, Jack Andrew, Lachlan L.H. Gan, Junhao Honorio, Jean Umboh, Seeun William 

作者机构：School of Computing and Information Systems University of Melbourne Australia 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Consensus algorithm 

摘      要：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(nk 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(nk logk n) algorithm. Copyright © 2024, The Authors. All rights reserved.