All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time

DOI10.1016/j.tcs.2008.01.032zbMath1140.68054OpenAlexW1601568173MaRDI QIDQ924140

Raphael Yuster

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

zbMATH Keywords

algorithmdirected acyclic graphfast matrix multiplicationcommon ancestor

Mathematics Subject Classification ID

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