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:2 (2003), 373-383.



Abstract

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}
}


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