Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/75856
Type: Artigo de periódico
Title: A GENERALIZATION OF THE MAXIMAL CLOSURE OF A DIGRAPH
Author: MACHADO, AF
PERIN, C
Abstract: 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}.
Subject: NONNUMERICAL ALGORITHMS AND PROBLEMS
COMBINATORICS
GRAPH THEORY
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Date Issue: 1992
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.