Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Stefan Eckhardt; Andreas Muehling; Johannes Nowak 
Titel:
Fast Lowest Common Ancestor Computations in Dags 
Abstract:
This work studies lowest common ancestor problems in directed acyclic graphs. We present fast algorithms for solving the All-Pairs Representative and All-Pairs All LCA problems with expected running time of O(n^2 log n) and O(n^3 loglog n) respectively. The speed-ups over recently developed methods are achieved by applying transitive reduction on the input dags. The algorithms are experimentally evaluated against previous approaches demonstrating a significant improvement. On the purely theoreti...    »
 
Stichworte:
Algorithms and complexity; graph theory; lowest common ancestor; directed acyclic graph; experimental algorithms 
Jahr:
2007 
Jahr / Monat:
2007-01-01 00:00:00 
Seiten/Umfang:
17