Covering skew-supermodular functions by hypergraphs of minimum total size
Megjelenés dátuma: 2009
Kolligátumi fejrekord: urn:issn:0167-6377
MTMT: 240381
WoS ID: 000271367300010
Scopus ID: 69549091716
Absztrakt:
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 p(1) and p(2) 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 p(1) and p(2). We also give some applications concerning the connectivity augmentation of hypergraphs. (C) 2009 Elsevier B.V. All rights reserved.