Istituto di Scienza e Tecnologie dell'Informazione     
Alia G., Maestrini P. On optimal partitions of weighted hypergraphs. Internal note IEI-B74-06, 1974.
The problem of determining optimal partitions of an hypergraphs is relevant in several areas, such as circuit design, information retrieval and program paging. In many cases there exist optimal or near optimal partitions, subject to the constraint that each block is an LS set. Intuitively, an LS set is a subset of nodes of the given hypergraph, more strongly connected to each other that to the nodes in the complementary subset. In this paper a polinomial-bounded procedure to determine all the LS sets in a given hypergraph is presented and it is shown that the proposed procedure is considerably faster than those previously knows. The procedure is based upon the representation of the given hypergraph with a " flow equivalent tree", into which a collection of subsets including all the LS sets is easily identified

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