A GENERALIZATION OF THE MAXIMAL CLOSURE OF A DIGRAPH

This paper studies the maximal closure problem and a generalization of this problem. A resolution of the first problem is proposed based on a transformation into a maximum, flow problem on a bipartite digraph, with overall complexity O(\V+\.(\V+\.\V-\+m)). Two iterative algorithms for the resolution of the second problem are presented. Each iteration involves the solution of a maximal closure problem. The first algorithm is theoretically simpler and its complexity is: O((SIGMA[u(i): i= 1,2..n]). \V+\.(\V+\.\V-\ +m)). The second one uses the scaling technique and has a complexity of: O(\V+\.(n.min(log2n,(log2C)1/2)+n.log2U.\V-\.\V+\+ m)). Where n is the number of vertices, m is the number of edges in the digraph, (V+,V-) is a bipartition of the set of vertices (V+={v(i):b(i) greater-than-or-equal-to 0} and V-={v(i):b(i) < 0}), C=max{c(ii):(v(i),v(j)) is-an-element-of E}, and U=max{d(ij):d(ij) is the length of the shortest directed path from v(i) is-an-element-of V+ to v(j) is-an-element-of max{u(i):i=1,2...n}.