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 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 @math of chains by following a greedy strategy. We show that, given a vertex topological order, such a decomposition is obtained in @math time, and requires @math space, with @math bounded by @math . 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.
An important feature of database support for expert systems is the ability of the database to answer queries regarding the existence of a path from one node to another in the directed graph underlying some database relation. Given just the database relation, answering such a query is time-consuming, but given the transitive closure of the database relation a table look-up suffices. We present an indexing scheme that permits the storage of the pre-computed transitive closure of a database relation in a compressed form. The existence of a specified tuple in the closure can be determined from this compressed store by a single look-up followed by an index comparision. We show how to add nodes and arcs to the compressed closure incrementally. We also suggest how this compression technique can be used to reduce the effort required to compute the transitive closure.