User: Guest  Login
Title:

A Path Cover Technique for LCAs in Dags

Document type:
Technical Report
Author(s):
Andrzej Lingas; Miroslaw Kowaluk; Johannes Nowak
Abstract:
We develop a path cover technique to solve lowest common ancestor (LCA for short) problems in a directed acyclic graph (dag). Our method yields improved upper bounds for two recently studied problem variants, computing one (representative) LCA for all pairs of vertices and computing all LCAs for all pairs of vertices. The bounds are expressed in terms of the number n of vertices and the so called width w(G) of the input dag G. For the first problem we achieve O(n2 w(G) polylog(n)) time which imp...     »
Keywords:
Algorithms and complexity; graph theory; lowest common ancestor; directed acyclic graph; path cover; width
Year:
2008
Year / month:
2008-04-01 00:00:00
Pages:
15
 BibTeX