Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Matthias Baumgart; Stefan Eckhardt; Jan Griebsch; Sven Kosub; Johannes Nowak 
Titel:
All-Pairs Common-Ancestor Problems in Weighted Dags 
Abstract:
This work considers the (lowest) common ancestor problem in weighted \\directed acyclic graphs. \\The minimum-weight (lowest) common ancestor of two vertices is the vertex \\ among the set of (lowest) common ancestors with the\\ smallest ancestral distance. For the all-pairs minimum-weight common\\ ancestor problem we present an O(nm) algorithm for arbitrary edge weights\\ which is optimal for sparse graphs and an O(n^2.575) algorithm for dense\\ graphs with moderately bounded edge weights based...    »
 
Stichworte:
Algorithms and complexity; graph theory; lowest common ancestor; directed acyclic graph 
Jahr:
2006 
Jahr / Monat:
2006-04-01 00:00:00 
Seiten/Umfang:
17