Premium
Cutsets and partitions of hypergraphs
Author(s) -
Lawler E. L.
Publication year - 1973
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230030306
Subject(s) - hypergraph , mathematics , computation , bounded function , combinatorics , set (abstract data type) , discrete mathematics , time complexity , graph , computer science , algorithm , mathematical analysis , programming language
A hypergraph is a combinatorial structure with nodes and arcs, similar to an ordinary „linear” graph, except that arcs are incident to arbitrary subsets of nodes, instead of pairs of nodes. Cutsets of hypergraphs are defined in a natural way, and it is shown that optimal cutsets can be found by means of a network flow computation. The optimal cutset computation can be used to generate a family of subsets of nodes, which we call LS sets. Intuitively, an LS set is a subset of nodes that are more strongly connected to each other than to nodes in the complementary set. LS sets are useful for constructing optimal or near‐optimal partitions of the nodes. A polynomial‐bounded partitioning algorithm is presented, and various applications are suggested.