Boost logo

Boost Users :

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-07-16 11:12:37

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.


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 <jsiek_at_[hidden]>
Ph.D. Student, Indiana University Bloomington
C++ Booster (

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at