On the Graph Decomposition

In this paper, we propose an efficient algorithm to decompose a directed acyclic graph (DAG) 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.