All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
From MaRDI portal
Publication:924140
DOI10.1016/j.tcs.2008.01.032zbMath1140.68054OpenAlexW1601568173MaRDI QIDQ924140
Publication date: 28 May 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.032
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A Path Cover Technique for LCAs in Dags ⋮ A \(\min\)-\(\max\) relation in flowgraphs and some applications
Cites Work
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- Fast rectangular matrix multiplication and applications
- Finding level-ancestors in trees
- Rectangular matrix multiplication revisited
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- Efficient determination of the transitive closure of a directed graph
- Fast Algorithms for Finding Nearest Common Ancestors
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
- Fast Lowest Common Ancestor Computations in Dags
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Lowest common ancestors in trees and directed acyclic graphs
- Automata, Languages and Programming
