A Path Cover Technique for LCAs in Dags

DOI10.1007/978-3-540-69903-3_21MaRDI QIDQ3512461zbMATH OpenOpenAlexFDO

Authors Mirosław Kowaluk, Johannes Nowak, Andrzej Lingas

Publication date 15 July 2008

Published in Algorithm Theory – SWAT 2008 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Finding least common ancestors in directed acyclic graphs
• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Automata, Languages and Programming
• Fast Lowest Common Ancestor Computations in Dags

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• A Path Cover Technique for LCAs in Dags
• A decomposition theorem for partially ordered sets
• Algorithms – ESA 2004
• All-Pairs Ancestor Problems in Weighted Dags
• All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An improved algorithm for transitive closure on acyclic digraphs
• Applications of Path Compression on Balanced Trees
• Automata, Languages and Programming
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast Lowest Common Ancestor Computations in Dags
• Fast rectangular matrix multiplication and applications
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Finding lowest common ancestors in arbitrarily directed trees
• Introduction to algorithms
• Lowest common ancestors in trees and directed acyclic graphs
• Matrix multiplication via arithmetic progressions
• On Finding Lowest Common Ancestors in Trees
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• Recognition algorithms for orders of small width and graphs of small Dilworth number
• Rectangular matrix multiplication revisited
• Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication

Cited in

(8)

• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• New common ancestor problems in trees and directed acyclic graphs
• Lowest common ancestors in trees and directed acyclic graphs
• Sparse dynamic programming on DAGs with small width
• A Path Cover Technique for LCAs in Dags
• All-Pairs Ancestor Problems in Weighted Dags
• All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended

This page was built for publication: A Path Cover Technique for LCAs in Dags

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