A new method for generating compressed representation of transitive closure
Yangjun Chen · 2008
Let G(V, E) be a digraph (directed graph) with n nodes and e edges. Digraph G* = (V, E*) is the reflexive, transitive closure of G if (v, u) ∈ E* iff there is a path from v to u in G. If we store it as a matrix, O(n2) space is required, not suitable for large graphs. In this paper, we present a new method to reduce the space overhead to O(bn), where b is the G's width, defined to be the size of a largest node subset U of G such that for every pair of nodes u, v ∈ U, there does not exist a path from u to v or from v to u. With such a compressed data structure of transitive closure, the time for checking reachability (whether a node is reachable from another node through a path) is bounded by O(logb). In addition, this data structure can be generated in O(be') time, where e' is the size of a subset of E, which contains only those edges (u, v) such that there is no path of length ≥2 connecting u and v. We are able to show that the average value of e' is on the order of O(n1.5). Our method is suitable for both acyclic and cyclic graphs.