1.4.5 Transitive Closure and Reduction

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A directed graph G=(V,E) .

Problem: For transitive closure, construct a graph G'=(V,E') with edge (i,j) \in E' iff there is a directed path from i to j in G . For transitive reduction, construct a small graph G'=(V,E') with a directed path from i to j in G' iff (i,j) \in E .

Implementations

  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 6)
  • Combinatorica (Mathematica) (rating 4)

    Related Problems

  • Connected Components
  • Shortest Path

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .