Hi Thomas, Here's a couple more references. However, I wasn't able to find the actual text online. A trip to the library may be in order. A. Goralcikova, V. Konbek: ``A Reduct and Closure Algorithm for Graphs''. Mathematical Foundations of Computer Science, LNCS 74, 301-307, 1979 David Gries, Alain J. Martin, Jan L. A. van de Snepscheut, and Jan Tijmen Udding. An algorithm for transitive reduction of an acyclic graph. Science of Computer Programming, 12(2):151--155, July 1989. -Jeremy On Jul 16, 2004, at 10:10 AM, Thomas Costa wrote:
I've looked for a decent algorithm and everyone seems to reference the Aho and Ullman paper from SIAM Computing 1972 which I cannot find online. The only algorithm I've come up with is for DAGs. Basic idea is to topo sort the DAG and then for each node in the DAG iterate over the children of it's highest topo order child and use this to prune direct edges to children that can be reached over a longer path. It seems kind of expensive so I'm wondering if there is a smarter way to do it. I have no real experience in graph computation past what I've picked up using BGL for a few months.
Jeremy Siek