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.

Excerpt from The Algorithm Design Manual: Transitive closure can be thought of as establishing a data structure that makes it possible to solve reachability questions (can I get to x from y?) efficiently. After the preprocessing of constructing the transitive closure, all reachability queries can be answered in constant time by simply reporting a matrix entry. Transitive closure is fundamental in propagating the consequences of modified attributes of a graph G. For example, consider the graph underlying any spreadsheet model, where the vertices are cells and there is an edge from cell $i$ to cell j if the result of cell j depends on cell i. When the value of a given cell is modified, the values of all reachable cells must also be updated. The identity of these cells is revealed by the transitive closure of G. Many database problems reduce to computing transitive closures, for analogous reasons.

The best book available for this problem is Leda : A Platform for Combinatorial and Geometric Computing by Kurt Mehlhorn and Stefan Naher.


Implementations

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

    Related Problems

  • Connected Components
  • Shortest Path


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .