On decomposing a hypergraph into k connected sub-hypergraphs

András Frank, Tamás Király, Matthias Kriesell

Published in:
Discrete Appl. Math. 131:2 (2003), 373-383.


We extend first the notion of graphic matroids for hypergraphs and apply then the matroid partition theorem of Edmonds to obtain a generalization of Tutte's disjoint trees theorem for hypergraphs. As a corollary, we prove for positive integers k and q that every (kq)-edge-connected hypergraph of rank q can be decomposed into k connected sub-hypergraphs, a well-known result for q=2. Another by-product is a sufficient condition for the existence of k edge-disjoint Steiner trees in a bipartite graph.

Hypergraph, Matroid, Steiner tree

Bibtex entry:

AUTHOR = {Frank, Andr{\'a}s and Kir{\'a}ly, Tam{\'a}s and Kriesell, Matthias},
TITLE = {On decomposing a hypergraph into $k$ connected sub-hypergraphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-02}

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