Journal
SIAM JOURNAL ON COMPUTING
Volume 34, Issue 4, Pages 894-923Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S0097539700370539
Keywords
LCA; dynamic LCA; cup-filling scheduling
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available