In this paper, we propose an efficient algorithm to decompose a directed acyclic graph G into a minimized set of node-disjoint chains, which cover all the nodes of G. For any two nodes u and v on a chain, if u is above v then there is a path from u to v in G. The best algorithm for this problem up to now needs O(n3) time, where n is the number of the nodes of G. Our algorithm, however, needs only O(k.n2) time, where k is G’s width, defined to be the size of a largest node subset U of G such that for every pair of nodes x, y∈U, there does not exist a path from x to y or from y to x. More importantly, by the existing algorithm, O(n2) extra space (besides the space for G itself) is required to maintain the transitive closure of G to do the task while ours needs only O(k.n) extra space.
展开▼
