Dynamic LCA queries on trees

Richard Cole, Ramesh Hariharan

Research output: Contribution to conferencePaper

Abstract

We show how to maintain 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.

Original languageEnglish (US)
Pages235-244
Number of pages10
StatePublished - 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Dynamic LCA queries on trees'. Together they form a unique fingerprint.

  • Cite this

    Cole, R., & Hariharan, R. (1999). Dynamic LCA queries on trees. 235-244. Paper presented at Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, .