Kurt Mehlhorn, Stefan NĂ¤her

Mentioned 1

LEDA is a library of efficient data types and algorithms and a platform for combinatorial and geometric computing on which application programs can be built. In each of the core computer science areas of data structures, graph and network algorithms, and computational geometry, LEDA covers all (and more) that is found in the standard textbooks. LEDA is the first such library; it is written in C++ and is available on many types of machine. Whilst the software is freely available worldwide and is installed at hundreds of sites, this is the first book devoted to the library. Written by the main authors of LEDA, it is the definitive account, describing how the system is constructed and operates and how it can be used. The authors supply ample examples from a range of areas to show how the library can be used in practice, making the book essential for all workers in algorithms, data structures and computational geometry.

Mentioned in questions and answers.

I have been looking for an algorithm to perform a transitive reduction on a graph, but without success. There's nothing in my algorithms bible (Introduction To Algorithms by Cormen et al) and whilst I've seen plenty of transitive closure pseudocode, I haven't been able to track down anything for a reduction. The closest I've got is that there is one in "Algorithmische Graphentheorie" by Volker Turau (ISBN:978-3-486-59057-9), but unfortunately I don't have access to this book! Wikipedia is unhelpful and Google is yet to turn up anything. :^(

Does anyone know of an algorithm for performing a transitive reduction?

The Wikipedia article on transitive reduction points to an implementation within GraphViz (which is open source). Not exactly pseudocode, but maybe someplace to start?

LEDA includes a transitive reduction algorithm. I don't have a copy of the LEDA book anymore, and this function might have been added after the book was published. But if it's in there, then there will be a good description of the algorithm.

Google points to an algorithm that somebody suggested for inclusion in Boost. I didn't try to read it, so maybe not correct?

Also, this might be worth a look.

Realated tags