Decomposing DAGs into Disjoint Chains

摘要

In this paper, we propose an efficient algorithm to decompose a directed acyclic graph (DAG) into chains, which has a lot of applications in computer science and engineering. Especially, it can be used to store transitive closures of directed graphs in an economical way. For a DAG G with n nodes, our algorithm needs O(n~2 + bn(b)) time to find a minimized set of disjoint chains, where b is G's width, defined to be the largest node subset U of G such that for every pair of nodes u,ν ∈ U, there does not exist a path from u to ν or from ν to u. Accordingly, the transitive closure of G can be stored in O(bn) space, and the reachability can be checked in O(logb) time. The method can also be extended to handle cyclic directed graphs.