Faster algorithms for finding lowest common ancestors in directed acyclic graphs
From MaRDI portal
Publication:2373733
Recommendations
- Fast Lowest Common Ancestor Computations in Dags
- Finding least common ancestors in directed acyclic graphs
- A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
- Finding lowest common ancestors in arbitrarily directed trees
- Lowest common ancestors in trees and directed acyclic graphs
- Fast Algorithms for Finding Nearest Common Ancestors
- scientific article; zbMATH DE number 4064469
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- A fast algorithm for finding the lowest common ancestor of two neighboring nodes in a complete binary tree
- A fast cost-optimal parallel algorithm for the lowest common ancestor problem
Cites work
- scientific article; zbMATH DE number 1512678 (Why is no real title available?)
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Applications of Path Compression on Balanced Trees
- Automata, Languages and Programming
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Dynamic LCA Queries on Trees
- Fast Algorithms for Finding Nearest Common Ancestors
- Fast rectangular matrix multiplication and applications
- Finding least common ancestors in directed acyclic graphs
- Finding lowest common ancestors in arbitrarily directed trees
- Introduction to algorithms
- Matrix multiplication via arithmetic progressions
- Rectangular matrix multiplication revisited
- Witnesses for Boolean matrix multiplication and for transitive closure
Cited in
(33)- Fast Algorithms for Finding Nearest Common Ancestors
- A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
- Fast smallest lowest common ancestor computation based on stable match
- scientific article; zbMATH DE number 7053319 (Why is no real title available?)
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Faster multi-witnesses for Boolean matrix multiplication
- Generalized rank-breaking: computational and statistical tradeoffs
- New common ancestor problems in trees and directed acyclic graphs
- Lowest common ancestors in trees and directed acyclic graphs
- Finding lowest common ancestors in arbitrarily directed trees
- (, +) matrix and vector products for inputs decomposable into few monotone subsequences
- \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
- Simplifying and characterizing DAGs and phylogenetic networks via least common ancestor constraints
- Extreme witnesses and their applications
- The heaviest induced ancestors problem: better data structures and applications
- Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
- Faster Algorithms for All Pairs Non-Decreasing Paths Problem
- Automata, Languages and Programming
- Algorithms, reductions and equivalences for small weight variants of all-pairs shortest paths
- Finding least common ancestors in directed acyclic graphs
- Extreme witnesses and their applications
- A fast output-sensitive algorithm for Boolean matrix multiplication
- All-pairs bottleneck paths in vertex weighted graphs
- Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
- A Path Cover Technique for LCAs in Dags
- Fast Lowest Common Ancestor Computations in Dags
- Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
- All-Pairs Ancestor Problems in Weighted Dags
- All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- A \(\min\)-\(\max\) relation in flowgraphs and some applications
- Improved time bounds for all pairs non-decreasing paths in general digraphs
- On minimum witnesses for Boolean matrix multiplication
This page was built for publication: Faster algorithms for finding lowest common ancestors in directed acyclic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373733)
