Re: [Boost-users] BGL transitive reduction algorithm?

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.

-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 <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Student, Indiana University Bloomington
C++ Booster (http://www.boost.org)
_______________________________________________