INPUT OUTPUT

**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.

Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica by S. Pemmaraju and S. Skiena | Handbook of Theoretical Computer Science : Algorithms and Complexity by J. Van Leeuwen | The Design and Analysis of Computer Algorithms by A. Aho and J. Hopcroft and J. Ullman |

This page last modified on 2008-07-10 . www.algorist.com