Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Andrzej Lingas; Miroslaw Kowaluk; Johannes Nowak 
Titel:
A Path Cover Technique for LCAs in Dags 
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...    »
 
Stichworte:
Algorithms and complexity; graph theory; lowest common ancestor; directed acyclic graph; path cover; width 
Jahr:
2008 
Jahr / Monat:
2008-04-01 00:00:00 
Seiten/Umfang:
15