Dynamic LCA Queries on Trees

DOI10.1137/S0097539700370539MaRDI QIDQ5317181zbMATH OpenOpenAlexFDO

Authors Ramesh Hariharan, Richard Cole

Publication date 16 September 2005

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539700370539

zbMATH Keywords

cup-filling schedulingdynamic LCALCA

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1305412
• Automata, Languages and Programming
• Dynamic trees in practice
• Conjunctive queries over trees
• Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees
• Dynamic tree algorithms
• Dynamic Trees with Almost-Optimal Access Cost
• Path minima queries in dynamic weighted trees
• Conjunctive query containment over trees

Cited in

(25)

• Recognizing weakly simple polygons
• A \(\min\)-\(\max\) relation in flowgraphs and some applications
• Leaf trees
• Computing longest (common) Lyndon subsequences
• Computing longest palindromic substring after single-character or block-wise edits
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Incremental algorithm for maintaining a DFS tree for undirected graphs
• scientific article; zbMATH DE number 1670815 (Why is no real title available?)
• Finding gapped palindromes online
• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
• On Dynamic DFS Tree in Directed Graphs
• Time-optimal top-k document retrieval
• Longest common subsequence in at least k length order-isomorphic substrings
• Compact separator decompositions in dynamic trees and applications to labeling schemes
• scientific article; zbMATH DE number 1305412 (Why is no real title available?)
• The online house numbering problem: min-max online list labeling
• Dynamic planar orthogonal point location in sublogarithmic time
• Longest substring palindrome after edit
• Searching in dynamic tree-like partial orders
• Inducing suffix and LCP arrays in external memory
• Automata, Languages and Programming
• Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees
• Computing longest Lyndon subsequences and longest common Lyndon subsequences
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Linear-size suffix tries and linear-size CDAWGs simplified and improved

This page was built for publication: Dynamic LCA Queries on Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317181)