A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
DOI10.1016/J.TCS.2013.09.030zbMATH Open1407.68351OpenAlexW2134439164WikidataQ60164249 ScholiaQ60164249MaRDI QIDQ391971FDOQ391971
Authors: Santanu Kumar Dash, Sven-Bodo Scholz, Stephan Herhut, Bruce Christianson 
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.09.030
Recommendations
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- Fast Lowest Common Ancestor Computations in Dags
- Finding least common ancestors in directed acyclic graphs
- Lowest common ancestors in trees and directed acyclic graphs
- Finding lowest common ancestors in arbitrarily directed trees
- scientific article; zbMATH DE number 4064469
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- A fast cost-optimal parallel algorithm for the lowest common ancestor problem
- Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees
- New common ancestor problems in trees and directed acyclic graphs
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Introduction to algorithms.
- Recursive Star-Tree Parallel Data Structure
- Title not available (Why is that?)
- Multiplying matrices faster than coppersmith-winograd
- Lowest common ancestors in trees and directed acyclic graphs
- Fast Algorithms for Finding Nearest Common Ancestors
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Rectangular matrix multiplication revisited
- 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
Cited In (7)
- Fast smallest lowest common ancestor computation based on stable match
- Finding lowest common ancestors in arbitrarily directed trees
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- Automata, Languages and Programming
- A Path Cover Technique for LCAs in Dags
- Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
- SAT solving using XOR-OR-AND normal forms.
This page was built for publication: A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q391971)
