Dynamic LCA queries on trees

被引：43
作者：
Cole, R
Hariharan, R
机构：
[1] NYU, Courant Inst Math Sci, Dept Comp Sci, New York, NY 10012 USA
[2] Indian Inst Sci, Dept Comp Sci & Automat, Bangalore 560012, Karnataka, India
来源：
SIAM JOURNAL ON COMPUTING | 2005年 / 34卷 / 04期
关键词：
LCA; dynamic LCA; cup-filling" scheduling;
D O I：
10.1137/S0097539700370539
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show how to maintain a data structure on trees which allows for the following operations, all in worst-case constant time: 1. insertion of leaves and internal nodes, 2. deletion of leaves, 3. deletion of internal nodes with only one child, 4. determining the least common ancestor of any two nodes. We also generalize the Dietz - Sleator "cup-filling" scheduling methodology, which may be of independent interest.
引用
收藏
页码：894 / 923
页数：30
相关论文
共 15 条
[1]   The LCA problem revisited [J].
Bender, MA ;
Farach-Colton, M .
LATIN 2000: THEORETICAL INFORMATICS, 2000, 1776 :88-94
[2]   FINDING LEVEL-ANCESTORS IN TREES [J].
BERKMAN, O ;
VISHKIN, U .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (02) :214-230
[3]   Approximate string matching: A simpler faster algorithm [J].
Cole, R ;
Hariharan, R .
SIAM JOURNAL ON COMPUTING, 2002, 31 (06) :1761-1782
[4]  
Dietz Paul, 1987, P 19 ANN ACM S THEOR, P365, DOI DOI 10.1145/28395.28434
[5]  
FARACHCOLTON M, 1999, COMMUNICATION
[6]  
GABOW HN, 1990, PROCEEDINGS OF THE FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P434
[7]  
GUSFIELD D, 1997, ALGORITHMS STRINGS T, P196
[8]   FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS [J].
HAREL, D ;
TARJAN, RE .
SIAM JOURNAL ON COMPUTING, 1984, 13 (02) :338-355
[9]   FAST PARALLEL AND SERIAL APPROXIMATE STRING MATCHING [J].
LANDAU, GM ;
VISHKIN, U .
JOURNAL OF ALGORITHMS, 1989, 10 (02) :157-169
[10]   SPACE-ECONOMICAL SUFFIX TREE CONSTRUCTION ALGORITHM [J].
MCCREIGHT, EM .
JOURNAL OF THE ACM, 1976, 23 (02) :262-272
12