Journal of Advances in Mathematics and Computer Science

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(n³) time, where n is the number of the nodes of G. Our algorithm, however, needs only O(k.n²) time, where k isG’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(n²) 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.