Cole, Richard ; Hariharan, Ramesh (2005) Dynamic LCA queries on trees SIAM Journal on Computing, 34 (4). pp. 894-923. ISSN 0097-5397
Full text not available from this repository.
Official URL: http://epubs.siam.org/doi/abs/10.1137/S00975397003...
Related URL: http://dx.doi.org/10.1137/S0097539700370539
Abstract
We show how to maintain a data structure on trees which allows for the following operations, all in worst-case constant time: insertion of leaves and internal nodes, deletion of leaves, deletion of internal nodes with only one child, 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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Society for Industrial and Applied Mathematics. |
| ID Code: | 102240 |
| Deposited On: | 09 Mar 2018 11:20 |
| Last Modified: | 09 Mar 2018 11:20 |
Repository Staff Only: item control page
