Hypergraph connectivity augmentation (Q1300056)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hypergraph connectivity augmentation |
scientific article |
Statements
Hypergraph connectivity augmentation (English)
0 references
5 December 1999
0 references
The hypergraph augmentation problem consists in augmenting a hypergraph by (``small'') hyperedges to meet prescribed local connectivity requirements. In the paper a minimax theorem for this problem is given. The result is derived from the degree-constrained version of the problem and for this version the required hypergraph is constructed in a greedy type algorithm. A similar minimax result is given for the problem of augmenting a hypergraph by weighted edges. The results have applications in supermodular colourings.
0 references
connectivity augmentation
0 references
greedy algorithm
0 references
hypergraph
0 references
skew-supermodular function
0 references
supermodular colouring
0 references