User: Guest  Login
Document type:
Technical Report 
Author(s):
Stefan Eckhardt; Andreas Muehling; Johannes Nowak 
Title:
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...    »
 
Keywords:
Algorithms and complexity; graph theory; lowest common ancestor; directed acyclic graph; experimental algorithms 
Year:
2007 
Year / month:
2007-01-01 00:00:00 
Pages:
17