Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 894-923 |
Number of pages | 30 |
Journal | SIAM Journal on Computing |
Volume | 34 |
Issue number | 4 |
DOIs | |
State | Published - 2005 |
Keywords
- "cup-filling" scheduling
- Dynamic LCA
- LCA
ASJC Scopus subject areas
- General Computer Science
- General Mathematics