Istituto di Scienza e Tecnologie dell'Informazione     
Alia G., Maestrini P. A procedure to determine optimal partitions of weighted hypergraphs through a network-flow analogy. In: Calcolo, vol. 13 (2) pp. 191 - 211. 1976.
Many problems arising in computer science and applications are amenable to finding optimal partitions of weighted hypergraphs or, more simply, of ordinary weighted graphs. As recently noted by some authors, in many cases the construction of optimal or near-optimal partitions is made easier if a family of subsets of nodes of the given hypergraph, called LS sets, is previously determined. Intuitively, an LS set is a subset of nodes of the hypergraph, which are more strongly connected to each-other than the nodes in the complementary subset. This paper presents a polynomial-bounded procedure to determine all the LS sets in a given weighted hypergraph. The proposed procedure, that is considerably faster than those previously known, is based upon a network-flow analogy and replaces the given hypergraph with a "flow equivalent" tree, into which a collection of subsets of nodes, which includes all LS sets, is easily determined.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional