Finding level-ancestors in trees
From MaRDI portal
Publication:1329158
DOI10.1016/S0022-0000(05)80002-9zbMath0806.68027WikidataQ56227296 ScholiaQ56227296MaRDI QIDQ1329158
Publication date: 29 June 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items
Longest common extensions in trees ⋮ Rectilinear short path queries among rectangular obstacles ⋮ Fingerprints in compressed strings ⋮ The level ancestor problem simplified ⋮ The suffix tree of a tree and minimizing sequential transducers ⋮ Longest Common Extensions in Trees ⋮ Algorithms for interval structures with applications ⋮ On geometric path query problems ⋮ Cross-document pattern matching ⋮ 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 ⋮ Succinct representations of permutations and functions ⋮ All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Fast Label Extraction in the CDAWG ⋮ Parallel rectilinear shortest paths with rectangular obstacles ⋮ Compressed subsequence matching and packed tree coloring ⋮ A \(\min\)-\(\max\) relation in flowgraphs and some applications ⋮ A linear‐time algorithm for broadcast domination in a tree ⋮ Unnamed Item ⋮ Center location problems on tree graphs with subtree-shaped customers ⋮ The Level-Ancestor problem on pure pointer machines ⋮ Faster queries for longest substring palindrome after block edit ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Real two dimensional scaled matching ⋮ Parallel construction and query of index data structures for pattern matching on square matrices ⋮ Small-space LCE data structure with constant-time queries ⋮ Succinct Representations of Ordinal Trees ⋮ Constructing LZ78 tries and position heaps in linear time for large alphabets ⋮ Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms.
Cites Work
- Unnamed Item
- Recognizing breadth-first search trees in linear time
- On efficient parallel strong orientation
- Computing on a free tree via complexity-preserving mappings
- Almost fully-parallel parentheses matching
- Faster optimal parallel prefix sums and list ranking
- Fast Algorithms for Finding Nearest Common Ancestors
- An Efficient Parallel Biconnectivity Algorithm
- Relations between Concurrent-Write Models of Parallel Computation
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Parallel Prefix Computation
- Finding the maximum, merging, and sorting in a parallel computation model
- Recursive Star-Tree Parallel Data Structure
- Parallel Tridiagonal Equation Solvers
