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 ?
Common Ancestor in a Directed Acyclic Graph (DAG)
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 ?
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
en1 | zeref_dragoneel | 2015-08-27 07:02:23 | 207 | Initial revision (published) |