Dynamic LCA Queries on Trees
From MaRDI portal
Publication:5317181
DOI10.1137/S0097539700370539zbMath1075.68019OpenAlexW2066362074MaRDI QIDQ5317181
Ramesh Hariharan, Richard John 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
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Data structures (68P05)
Related Items (19)
Faster algorithms for finding lowest common ancestors in directed acyclic graphs ⋮ Compact separator decompositions in dynamic trees and applications to labeling schemes ⋮ Computing longest (common) Lyndon subsequences ⋮ Full-fledged real-time indexing for constant size alphabets ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ On Dynamic DFS Tree in Directed Graphs ⋮ Recognizing weakly simple polygons ⋮ Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees ⋮ Computing longest Lyndon subsequences and longest common Lyndon subsequences ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ A \(\min\)-\(\max\) relation in flowgraphs and some applications ⋮ Unnamed Item ⋮ Finding Gapped Palindromes Online ⋮ Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing ⋮ The Online House Numbering Problem: Min-Max Online List Labeling ⋮ Inducing Suffix and LCP Arrays in External Memory ⋮ Longest substring palindrome after edit
This page was built for publication: Dynamic LCA Queries on Trees
