Common Ancestor in a Directed Acyclic Graph (DAG)

Revision en1, by zeref_dragoneel, 2015-08-27 07:02:23

I need to find all pairs of nodes which have a common ancestor in a DAG in O(n^2 + m) time. I can use O(n^2 memory).

Please suggest a method to do this ?

Tags graphs, dag, lca

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English zeref_dragoneel 2015-08-27 07:02:23 207 Initial revision (published)