TR-2002-11

A note on hypergraph connectivity augmentation

Tamás Király, Márton Makai



Abstract

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:

@techreport{egres-02-11,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Makai, M{\'a}rton},
TITLE = {A note on hypergraph connectivity augmentation},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-11}
}


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