Covering skew-supermodular functions by hypergraphs of minimum total size

Covering skew-supermodular functions by hypergraphs of minimum total size

0.00 Avg rating0 Votes
Article ID: iaor20102983
Volume: 37
Issue: 5
Start Page Number: 345
End Page Number: 350
Publication Date: Sep 2009
Journal: Operations Research Letters
Authors: ,
Keywords: graphs
Abstract:

The paper presents results related to a theorem of Szigeti on covering symmetric skew-supermodular set functions by hypergraphs. We prove the following generalization using a variation of Schrijver's supermodular colouring theorem: if p1 and p2 are skew-supermodular functions with the same maximum value, then it is possible to find in polynomial time a hypergraph of minimum total size that covers both p1 and p2. We also give some applications concerning the connectivity augmentation of hypergraphs.

Reviews

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