A Path Cover Technique for LCAs in Dags
From MaRDI portal
Publication:3512461
DOI10.1007/978-3-540-69903-3_21zbMath1155.68476OpenAlexW1760533781MaRDI QIDQ3512461
Johannes Nowak, Mirosław Kowaluk, 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
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) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A scalable approach to computing representative lowest common ancestor in directed acyclic graphs ⋮ A Path Cover Technique for LCAs in Dags ⋮ New common ancestor problems in trees and directed acyclic graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
- An improved algorithm for transitive closure on acyclic digraphs
- 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
- A decomposition theorem for partially ordered sets
- Applications of Path Compression on Balanced Trees
- On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
- 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
- Fast Lowest Common Ancestor Computations in Dags
- All-Pairs Ancestor Problems in Weighted Dags
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- On Finding Lowest Common Ancestors in Trees
- Algorithms – ESA 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Lowest common ancestors in trees and directed acyclic graphs
- Automata, Languages and Programming
This page was built for publication: A Path Cover Technique for LCAs in Dags
