Algorithmic Methods for Lowest Common Ancestor Problems in Directed Acyclic Graphs
Johannes Nowak · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2009
Lowest common ancestor (LCA) problems in directed acyclic graphs (dags) have attracted scientific interest in the recent years.Directed acyclic graphs are powerful tools for modeling causality systems or other kind of entity dependencies, and efficient solutions to the respective lowest common ancestor problems are indispensable computational tools with regard to proper analysis of these systems.Similar problems in trees are widely understood, however, the generalizations to dags fall short of achieving comparable efficiencies.