Faster algorithms for finding lowest common ancestors in directed acyclic graphs

DOI10.1016/j.tcs.2007.02.053zbMath1118.68102OpenAlexW2162118804MaRDI QIDQ2373733

Mirosław Kowaluk, Artur Czumaj, Andrzej Lingas

Publication date: 16 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.053

zbMATH Keywords

time complexitydirected acyclic graphsmatrix multiplicationlowest common ancestors

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (16)

Quantum and approximation algorithms for maximum witnesses of Boolean matrix products ⋮ Extreme Witnesses and Their Applications ⋮ A scalable approach to computing representative lowest common ancestor in directed acyclic graphs ⋮ A Path Cover Technique for LCAs in Dags ⋮ All-pairs bottleneck paths in vertex weighted graphs ⋮ A fast output-sensitive algorithm for Boolean matrix multiplication ⋮ All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time ⋮ Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs ⋮ On minimum witnesses for Boolean matrix multiplication ⋮ A \(\min\)-\(\max\) relation in flowgraphs and some applications ⋮ Faster multi-witnesses for Boolean matrix multiplication ⋮ Unnamed Item ⋮ New common ancestor problems in trees and directed acyclic graphs ⋮ Extreme witnesses and their applications ⋮ Faster Algorithms for All Pairs Non-Decreasing Paths Problem ⋮ Unnamed Item

Cites Work

• Matrix multiplication via arithmetic progressions
• Witnesses for Boolean matrix multiplication and for transitive closure
• Fast rectangular matrix multiplication and applications
• Finding lowest common ancestors in arbitrarily directed trees
• Rectangular matrix multiplication revisited
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Applications of Path Compression on Balanced Trees
• Fast Algorithms for Finding Nearest Common Ancestors
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Dynamic LCA Queries on Trees
• Automata, Languages and Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Faster algorithms for finding lowest common ancestors in directed acyclic graphs