Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
From MaRDI portal
Publication:3527218
DOI10.1007/978-3-540-75520-3_25zbMath1151.68429OpenAlexW1532794166MaRDI QIDQ3527218
Mirosław Kowaluk, Andrzej Lingas
Publication date: 25 September 2008
Published in: Algorithms – ESA 2007 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-75520-3_25
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (7)
A scalable approach to computing representative lowest common ancestor in directed acyclic graphs ⋮ A Path Cover Technique for LCAs in Dags ⋮ Are unique subgraphs not easier to find? ⋮ All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time ⋮ Faster multi-witnesses for Boolean matrix multiplication ⋮ New common ancestor problems in trees and directed acyclic graphs ⋮ Unique subgraphs are not easier to find
This page was built for publication: Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
