A scalable approach to computing representative lowest common ancestor in directed acyclic graphs

DOI10.1016/J.TCS.2013.09.030MaRDI QIDQ391971zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

directed acyclic graphlowest common ancestors

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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

Cites work

• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• A Path Cover Technique for LCAs in Dags
• All-Pairs Ancestor Problems in Weighted Dags
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast Lowest Common Ancestor Computations in Dags
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Introduction to algorithms.
• Lowest common ancestors in trees and directed acyclic graphs
• Multiplying matrices faster than coppersmith-winograd
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• Rectangular matrix multiplication revisited
• Recursive Star-Tree Parallel Data Structure
• Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication

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)