A note on hypergraph connectivity augmentation

Tamás Király, Márton Makai


We prove an abstract version of an edge-splitting theorem for directed hypergraphs that appeared in [Berg, Jackson, Jordán], and use this result to obtain min-max theorems on hypergraph augmentation problems that are linked to orientations. These problems include (k,l)-edge-connectivity augmentation of directed hypergraphs, and (k,l)-partition-connectivity augmentation of undirected hypergraphs by uniform hyperedges.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Makai, M{\'a}rton},
TITLE = {A note on hypergraph connectivity augmentation},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-11}

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