The level ancestor problem simplified
From MaRDI portal
Publication:596133
DOI10.1016/j.tcs.2003.05.002zbMath1068.68047OpenAlexW3042165818WikidataQ57311753 ScholiaQ57311753MaRDI QIDQ596133
Martín Farach-Colton, Michael A. Bender
Publication date: 10 August 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2003.05.002
Related Items (57)
Efficiently computing runs on a trie ⋮ Longest common extensions in trees ⋮ Finding Articulation Points of Large Graphs in Linear Time ⋮ Position heaps for Cartesian-tree matching on strings and tries ⋮ Self-indexed Text Compression Using Straight-Line Programs ⋮ Fingerprints in compressed strings ⋮ Mincut sensitivity data structures for the insertion of an edge ⋮ On finding the Adams consensus tree ⋮ Parallel construction of succinct trees ⋮ Longest Common Extensions in Trees ⋮ Efficient Oracles and Routing Schemes for Replacement Paths ⋮ Cross-document pattern matching ⋮ Tight bound for the number of distinct palindromes in a tree ⋮ Absent Subsequences in Words ⋮ Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees ⋮ Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees ⋮ Unnamed Item ⋮ Fast layout computation of clustered networks: algorithmic advances and experimental analysis ⋮ Balancing graph Voronoi diagrams with one more vertex ⋮ Absent subsequences in words ⋮ Generalized substring compression ⋮ Range Medians ⋮ Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Mincut Sensitivity Data Structures for the Insertion of an Edge ⋮ Fast Label Extraction in the CDAWG ⋮ Simple and efficient fully-functional succinct trees ⋮ Faster Lyndon factorization algorithms for SLP and LZ78 compressed text ⋮ Shortest-Path Queries in Geometric Networks ⋮ Compressed subsequence matching and packed tree coloring ⋮ Efficient counting of square substrings in a tree ⋮ Morphing tree drawings in a small 3D grid ⋮ \(L_{1}\) shortest path queries in simple polygons ⋮ A linear‐time algorithm for broadcast domination in a tree ⋮ On compact representations of all-pairs-shortest-path-distance matrices ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Faster algorithms for computing the R* consensus tree ⋮ Ramsey partitions and proximity data structures ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Internal dictionary matching ⋮ Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning ⋮ Efficient computation of longest single-arm-gapped palindromes in a string ⋮ Covering uncertain points in a tree ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Computing runs on a trie ⋮ Faster queries for longest substring palindrome after block edit ⋮ A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners ⋮ Top tree compression of tries ⋮ Constant delay traversal of grammar-compressed graphs with bounded rank ⋮ Small-space LCE data structure with constant-time queries ⋮ Tree path majority data structures ⋮ Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs ⋮ Constructing LZ78 tries and position heaps in linear time for large alphabets ⋮ Longest Lyndon Substring After Edit ⋮ Succinct dynamic cardinal trees
Cites Work
This page was built for publication: The level ancestor problem simplified
