What are some good algorithms for the transitive reduction problem (either for general directed graphs or for DAGs)? In particular I am told that there are algorithms that match the running time of transitive closure algorithms. I have searched for a site that explains enough information to actually implement a solution, but I have not found one. I have also found some papers about the topic, which, unfortunately, I am not actually able to read (grrr... I want open access...)

  • created

    Nov '09
  • last reply

    Nov '09
  • 1

    reply

  • 222

    views

  • 2

    users

Transitive Reduction is simply the reverse of Transitive Closure.

Assuming a DAG, For each edge (u,v), if there exists a node w, with edges (u,w) and (w,v), such that |(u,w)| + |(w,v)| == |(u,v)| then delete the edge (u,v).

This can be solved easily in O(n^3) where n is the number of nodes using Floyd-Warshall.

Suggested Topics

Want to read more? Browse other topics in Off-topic or view latest topics.