Dynamic LCA queries on trees

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


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