Hypergraph connectivity augmentation

Hypergraph connectivity augmentation

0.00 Avg rating0 Votes
Article ID: iaor20001722
Country: Germany
Volume: 84
Issue: 3
Start Page Number: 519
End Page Number: 527
Publication Date: Jan 1999
Journal: Mathematical Programming
Authors:
Keywords: hypergraphs
Abstract:

The hypergraph augmentation problem is to augment a hypergraph by hyperedges to meet prescribed local connectivity requirements. We provide here a minimax theorem for this problem. The result is derived from the degree constrained version of the problem by a standard method. We shall construct the required hypergraph for the latter problem by a greedy type algorithm. A similar minimax result will be given for the problem of augmenting a hypergraph by weighted edges (hyperedges of size two with weights) to meet prescribed local connectivity requirements. Moreover, a special case of an earlier result of Schrijver on supermodular colourings shall be derived from our theorem.

Reviews

Required fields are marked *. Your email address will not be published.