Faster algorithms for finding lowest common ancestors in directed acyclic graphs

DOI10.1016/J.TCS.2007.02.053zbMATH Open1118.68102OpenAlexW2162118804MaRDI QIDQ2373733FDOQ2373733

Mirosław Kowaluk, Artur Czumaj, Andrzej Lingas

Publication date: 16 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.053

Recommendations

• Fast Lowest Common Ancestor Computations in Dags
• Finding least common ancestors in directed acyclic graphs
• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Finding lowest common ancestors in arbitrarily directed trees
• Lowest common ancestors in trees and directed acyclic graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• scientific article
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• A fast algorithm for finding the lowest common ancestor of two neighboring nodes in a complete binary tree
• A fast cost-optimal parallel algorithm for the lowest common ancestor problem

zbMATH Keywords

matrix multiplicationdirected acyclic graphstime complexitylowest 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) Analysis of algorithms (68W40) Paths and cycles (05C38)

Cites Work

• Introduction to algorithms
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Title not available (Why is that?)
• Matrix multiplication via arithmetic progressions
• Applications of Path Compression on Balanced Trees
• Fast Algorithms for Finding Nearest Common Ancestors
• Dynamic LCA Queries on Trees
• Fast rectangular matrix multiplication and applications
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Finding lowest common ancestors in arbitrarily directed trees
• Rectangular matrix multiplication revisited
• Finding least common ancestors in directed acyclic graphs
• Witnesses for Boolean matrix multiplication and for transitive closure
• Automata, Languages and Programming

Cited In (30)

• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Fast smallest lowest common ancestor computation based on stable match
• Title not available (Why is that?)
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Faster multi-witnesses for Boolean matrix multiplication
• New common ancestor problems in trees and directed acyclic graphs
• Lowest common ancestors in trees and directed acyclic graphs
• Finding lowest common ancestors in arbitrarily directed trees
• \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
• The heaviest induced ancestors problem: better data structures and applications
• Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs
• Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
• Faster Algorithms for All Pairs Non-Decreasing Paths Problem
• Automata, Languages and Programming
• Finding least common ancestors in directed acyclic graphs
• Extreme witnesses and their applications
• A fast output-sensitive algorithm for Boolean matrix multiplication
• A Path Cover Technique for LCAs in Dags
• All-pairs bottleneck paths in vertex weighted graphs
• Fast Lowest Common Ancestor Computations in Dags
• Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
• Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
• All-Pairs Ancestor Problems in Weighted Dags
• Title not available (Why is that?)
• Extreme Witnesses and Their Applications
• All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• A \(\min\)-\(\max\) relation in flowgraphs and some applications
• On minimum witnesses for Boolean matrix multiplication
• Fast Algorithms for Finding Nearest Common Ancestors

This page was built for publication: Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373733)