Thomas Haas
Thomas Haas

Reputation: 11

Computing classes of maximal path-equivalent nodes in a rooted DAG

I have a rooted directed acyclic graph with a single root node r. I'm interested in computing the following equivalence:

"Nodes v and w are maximal path-equivalent iff every maximal path from r contains either both of v and w or none of them"

In particular, I want to find all equivalence classes w.r.t. the above condition, possibly in O(n+m) time (n nodes, m edges). I feel like this problem is not unknown but I don't know what terms to search for. If anyone knows what this problem is called or has any ideas on how to solve it, I would appreciate it.

Upvotes: 1

Views: 30

Answers (0)

Related Questions