Lowest common ancestors in trees and directed acyclic graphs
From MaRDI portal
Publication:5711726
DOI10.1016/j.jalgor.2005.08.001zbMath1085.68103OpenAlexW1963838724WikidataQ29541159 ScholiaQ29541159MaRDI QIDQ5711726
Martín Farach-Colton, Giridhar Pemmasani, Pavel Sumazin, Michael A. Bender, Steven S. Skiena
Publication date: 8 December 2005
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jalgor.2005.08.001
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (52)
Compatibility of partitions with trees, hierarchies, and split systems ⋮ Efficient computation of sequence mappability ⋮ Optimal Encodings for Range Top-$$k$$, Selection, and Min-Max ⋮ Computing suffix links for suffix trees and arrays ⋮ On the range maximum-sum segment query problem ⋮ Succinct posets ⋮ The range 1 query (R1Q) problem ⋮ Efficient testing and matching of deterministic regular expressions ⋮ Computing longest (common) Lyndon subsequences ⋮ Space-time trade-offs for finding shortest unique substrings and maximal unique matches ⋮ Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs ⋮ A scalable approach to computing representative lowest common ancestor in directed acyclic graphs ⋮ Property Suffix Array with Applications in Indexing Weighted Sequences ⋮ Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees ⋮ Computing longest Lyndon subsequences and longest common Lyndon subsequences ⋮ Finding range minima in the middle: approximations and applications ⋮ A Path Cover Technique for LCAs in Dags ⋮ The nearest colored node in a tree ⋮ Efficient semi-external depth-first search ⋮ All-pairs bottleneck paths in vertex weighted graphs ⋮ Efficient algorithms for local ranking ⋮ Finding maximum sum segments in sequences with uncertainty ⋮ All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time ⋮ Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ A simple linear-space data structure for constant-time range minimum query ⋮ LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations ⋮ A \(\min\)-\(\max\) relation in flowgraphs and some applications ⋮ Computing the coarseness with strips or boxes ⋮ On Cartesian trees and range minimum queries ⋮ On space efficient two dimensional range minimum data structures ⋮ Computing optimal shortcuts for networks ⋮ Cache-oblivious index for approximate string matching ⋮ Range mode and range median queries in constant time and sub-quadratic space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New common ancestor problems in trees and directed acyclic graphs ⋮ A decomposition theorem and two algorithms for reticulation-visible networks ⋮ Internal dictionary matching ⋮ Indexing weighted sequences: neat and efficient ⋮ String periods in the order-preserving model ⋮ Exploratory knowledge discovery over web of data ⋮ Unnamed Item ⋮ A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time ⋮ Efficient representation and counting of antipower factors in words ⋮ Kinetic maintenance of mobile \(k\)-centres on trees ⋮ Faster entropy-bounded compressed suffix trees ⋮ Tree path majority data structures ⋮ Compressing dictionary matching index via sparsification technique ⋮ Linear-space data structures for range frequency queries on arrays and trees ⋮ Succinct dynamic cardinal trees
Uses Software
This page was built for publication: Lowest common ancestors in trees and directed acyclic graphs
