On the DAG Decomposition into Minimum Number of Chains
Research and Applications Towards Mathematics and Computer Science Vol. 1,
27 May 2023
,
Page 121-163
https://doi.org/10.9734/bpi/ratmcs/v1/5816E
Abstract
By the DAG decomposition, we mean the decomposition of 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. In this paper, we discuss an efficient algorithm for this problem. Its time complexity is bounded by O(max{k, } ×n2) while the best algorithm for this problem up to now needs O(n3) time, where n is the number of the nodes of G, and 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. k is in general much smaller than n. In addition, by the existing algorithm, Q(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. This is particularly important for some nowadays applications with massive graphs including millions and even billions of nodes, like the facebook, twitter, and some other social networks.
- Reachability queries
- directed graphs
- transitive closure
- graph decomposition
- chains