Fast Lowest Common Ancestor Computations in Dags

DOI10.1007/978-3-540-75520-3_62MaRDI QIDQ3527260zbMATH OpenOpenAlexFDO

Authors Stefan Eckhardt, Andreas Michael Mühling, Johannes Nowak

Publication date 25 September 2008

Published in Algorithms – ESA 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-75520-3_62

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Lowest common ancestors in trees and directed acyclic graphs
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Automata, Languages and Programming
• All-Pairs Ancestor Problems in Weighted Dags
• Finding least common ancestors in directed acyclic graphs

Cited in

(14)

• A \(\min\)-\(\max\) relation in flowgraphs and some applications
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Fast smallest lowest common ancestor computation based on stable match
• Tight bounds for the performance of Longest In System on DAGs
• Fast Algorithms for Finding Nearest Common Ancestors
• A Path Cover Technique for LCAs in Dags
• Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
• All-Pairs Ancestor Problems in Weighted Dags
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Lowest common ancestors in trees and directed acyclic graphs
• All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
• Faster multi-witnesses for Boolean matrix multiplication
• New common ancestor problems in trees and directed acyclic graphs

This page was built for publication: Fast Lowest Common Ancestor Computations in Dags

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3527260)