FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS

作     者：HAREL, D TARJAN, RE 

作者机构：UNIV NEW HAMPSHIREDURHAMNH 03824 BELL TEL LABS INCMURRAY HILLNJ 07974 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1984年第13卷第2期

页      面：338-355页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：graph algorithm nearest common ancestor tree inverse Ackermann’s function random access machine computational complexity 

摘      要：We consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, “What is the nearest common ancester of vertices x and y? We show that any pointer machine that solves this problem requires (loglogn) role=presentationΩ(loglogn)span style=display: inline-block; overflow: hidden; vertical-align: -0.352em; border-left: 0px solid; width: