Transitive reduction

[bbi5291]

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...)

[leppyr64]

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.