TR-2002-02

Covering symmetric supermodular functions by uniform hypergraphs

Tamás Király

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



Abstract

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:

@techreport{egres-02-02,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s},
TITLE = {Covering symmetric supermodular functions by uniform hypergraphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-02}
}


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