Covering symmetric supermodular functions by uniform hypergraphs

Tamás Király

Published in:
Journal of Combinatorial Theory Ser B. 91 (2004), 185-200.


We consider the problem of finding a uniform hypergraph that satisfies cut demands defined by a symmetric crossing supermodular set function. We give min-max formulas for both the degree specified and the minimum cardinality problem. These results include as a special case a formula on the minimum number of r-hyperedges whose addition to an initial hypergraph will make it k-edge-connected.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Tam{\'a}s},
TITLE = {Covering symmetric supermodular functions by uniform hypergraphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-02}

Last modification: 13.3.2018. Please email your comments to Tamás Király!