transitive reduction algorithm: pseudocode?

user_205207 0
Viewed 16845

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?

pseudocode graph algorithm
7 Answers

The basic gist of the transitive reduction algorithm I used is


foreach x in graph.vertices
   foreach y in graph.vertices
      foreach z in graph.vertices
         delete edge xz if edges xy and yz exist

The transitive closure algorithm I used in the same script is very similar but the last line is


         add edge xz if edges xy and yz OR edge xz exist
user_2052070
Related