Fast Lowest Common Ancestor Computations in Dags

DOI10.1007/978-3-540-75520-3_62zbMath1151.68736OpenAlexW1561486811MaRDI QIDQ3527260

Stefan Eckhardt, Andreas Michael Mühling, Johannes Nowak

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_62

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

A scalable approach to computing representative lowest common ancestor in directed acyclic graphs ⋮ A Path Cover Technique for LCAs in Dags ⋮ All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time ⋮ A \(\min\)-\(\max\) relation in flowgraphs and some applications ⋮ Faster multi-witnesses for Boolean matrix multiplication ⋮ New common ancestor problems in trees and directed acyclic graphs

This page was built for publication: Fast Lowest Common Ancestor Computations in Dags