Dynamic LCA queries on trees

Richard Cole; Ramesh Hariharan

doi:10.1137/S0097539700370539

Dynamic LCA queries on trees

Richard Cole, Ramesh Hariharan

Computer Science

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.1137/S0097539700370539
State	Published - 2005

Keywords

"cup-filling" scheduling
Dynamic LCA
LCA

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/S0097539700370539

Cite this

@article{2af0cddeff7a4a7b9b4627976d7f6b25,

title = "Dynamic LCA queries on trees",

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.",

keywords = "{"}cup-filling{"} scheduling, Dynamic LCA, LCA",

author = "Richard Cole and Ramesh Hariharan",

year = "2005",

doi = "10.1137/S0097539700370539",

language = "English (US)",

volume = "34",

pages = "894--923",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Dynamic LCA queries on trees

AU - Cole, Richard

AU - Hariharan, Ramesh

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

KW - "cup-filling" scheduling

KW - Dynamic LCA

KW - LCA

UR - http://www.scopus.com/inward/record.url?scp=24344478191&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=24344478191&partnerID=8YFLogxK

U2 - 10.1137/S0097539700370539

DO - 10.1137/S0097539700370539

M3 - Article

AN - SCOPUS:24344478191

SN - 0097-5397

VL - 34

SP - 894

EP - 923

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 4

ER -

Dynamic LCA queries on trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this