2021/05/05 by Tianqi Yang, Yang, Tianqi
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.2 #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2105.01864
openalex publication_date 2021/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Tree path minimum query problem is a fundamental problem while processing trees, and is used widely in minimum spanning tree verification and randomized minimum spanning tree algorithms. In this paper, we study the possibility of building an oracle in advance, which is able to answer the queries efficiently. We present an algorithm based on Boruvka trees. Our algorithm is the first to achieve a near-optimal bound on query time, while matching the currently optimal trade-off between construction time and the number of comparisons required at query. Particularly, in order to answer each query within 2k comparisons, our algorithm requires O(n log λk(n)) time and space to construct the oracle, and the oracle can answer queries in O(k + log λk(n)) time. Here λk(n) is the inverse of the Ackermann function along the k-th column. This algorithm not only is simpler than the previous ones, but also gives a completely different method of solving this problem.