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

DOI10.1016/j.tcs.2013.09.030zbMath1407.68351OpenAlexW2134439164WikidataQ60164249 ScholiaQ60164249MaRDI QIDQ391971

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• 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
• Recursive Star-Tree Parallel Data Structure
• Multiplying matrices faster than coppersmith-winograd
• Lowest common ancestors in trees and directed acyclic graphs

This page was built for publication: A scalable approach to computing representative lowest common ancestor in directed acyclic graphs