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.
展开▼
