期刊
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC
卷 57, 期 2, 页码 75-94出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jalgor.2005.08.001
关键词
lowest common ancestor (LCA); directed cyclic graph (DAG); range minimum query (RMQ); shortest path; Cartesian tree
We study the problem of finding lowest common ancestors (LCA) in trees and directed acyclic graphs (DAGs). Specifically, we extend the LCA problem to DAGs and study the LCA variants that arise in this general setting. We begin with a clear exposition of Berkman and Vishkin's simple optimal algorithm for LCA in trees. Their ideas Jay the foundation for our work on LCA problems in DAGs. We present an algorithm that finds all-pairs-representative LCA in DAGs in O(n(2.688)) operations, provide a transitive-closure lower bound for the all-pairs-representative-LCA problem, and develop an LCA-existence algorithm that preprocesses the DAG in transitive-closure time. We also present a suboptimal but practical O(n(3)) algorithm for all-pairs-representative LCA in DAGs that uses ideas from the optimal algorithms in trees and DAGs. Our results reveal a close relationship between the LCA, all-pairs-shortest-path, and transitive-closure problems. We conclude the paper with a short experimental study of LCA algorithms in trees and DAGs. Our experiments and source code demonstrate the elegance of the preprocessing-query algorithms for LCA in trees. We show that for most trees the suboptimal Theta (n log n)-preprocessing Theta (1)-query algorithm should be preferred, and demonstrate that our proposed O (n(3)) algorithm for all-pairs-representative LCA in DAGs performs well in both low and high density DAGs. (c) 2005 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据