  Several modern applications involve huge graphs and require fast answers to
reachability queries. In more than two decades since first proposals, several
approaches have been presented adopting on-line searches, hop labelling or
transitive closure compression. Transitive closure compression techniques
usually construct a graph reachability index, for example by decomposing the
graph into disjoint chains. As memory consumption is proportional to the number
of chains, the target of those algorithms is to decompose the graph into an
optimal number \width\ of chains. However, commonly used techniques fail to
meet general expectations, are exceedingly complex, and their application on
large graphs is impractical. The main contribution of this paper is a novel
approach to construct such reachability indexes. The proposed method decomposes
the graph into a sub-optimal number $\widehat{c}$ of chains by following a
greedy strategy. We show that, given a vertex topological order, such a
decomposition is obtained in $\mathcal{O}(\widehat{c} m)$ time, and requires
$\mathcal{O}(\widehat{c} n)$ space, with $\widehat{c}$ bounded by $[c
\log(\frac{n}{c})]$. We provide experimental evidence suggesting that, on
different categories of automatically generated benchmarks as well as on graphs
arising from the field of logic synthesis and formal verification, the proposed
method produces a number of chains very close to the optimum, while
significantly reducing computation time.
