TR-2001-02

On decomposing a hypergraph into k connected sub-hypergraphs

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

Published in:
Discrete Appl. Math. 131 (2003), no. 2, 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.

Keywords:
Hypergraph, Matroid, Steiner tree

Bibtex entry:

@techreport{egres-01-02,

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 www.cs.elte.hu/egres}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2001},
NUMBER	=	{TR-2001-02}

}