Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
LCA Queries in Directed Acyclic Graphs
verfasst von : Miroslaw Kowaluk, Andrzej Lingas
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present two methods for finding a lowest common ancestor (LCA) for each pair of vertices of a directed acyclic graph (dag) on
n
vertices and
m
edges.
The first method is surprisingly natural and solves the all-pairs LCA problem for the input dag on
n
vertices and
m
edges in time
O
(
nm
). As a corollary, we obtain an
O
(
n
2
)-time algorithm for finding genealogical distances considerably improving the previously known
O
(
n
2.575
) time-bound for this problem.
The second method relies on a novel reduction of the all-pairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem and hence also the all-pairs LCA problem in time
$O(n^{{2}+\frac{1}{4-\omega}})$
, where
ω
=2.376 is the exponent of the fastest known matrix multiplication algorithm. This improves the previously known
$O(n^{\frac{\omega+3}{2}})$
time-bound for the general all-pairs LCA problem in dags.