A Path Cover Technique for LCAs in Dags
DOI10.1007/978-3-540-69903-3_21zbMATH Open1155.68476OpenAlexW1760533781MaRDI QIDQ3512461FDOQ3512461
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
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
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)
Cites Work
- Introduction to algorithms
- Title not available (Why is that?)
- Algorithms – ESA 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Lowest common ancestors in trees and directed acyclic graphs
- Matrix multiplication via arithmetic progressions
- Applications of Path Compression on Balanced Trees
- On Finding Lowest Common Ancestors in Trees
- A decomposition theorem for partially ordered sets
- Fast Algorithms for Finding Nearest Common Ancestors
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Fast rectangular matrix multiplication and applications
- Finding lowest common ancestors in arbitrarily directed trees
- Rectangular matrix multiplication revisited
- Recognition algorithms for orders of small width and graphs of small Dilworth number
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
- A Path Cover Technique for LCAs in Dags
- Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
- Fast Lowest Common Ancestor Computations in Dags
- All-Pairs Ancestor Problems in Weighted Dags
- Automata, Languages and Programming
- An improved algorithm for transitive closure on acyclic digraphs
- All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
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)
