Published in:
Generalizing Kaneko's long path packing problem, Hartvigsen, Hell and Szabó [2] consider a new type of undirected graph packing problem, called the k-piece packing problem. A k-piece is a simple, connected graph with highest degree exactly k, so when k=1 we get the classical matching problem. They give a polynomial algorithm, a Tutte-type characterization and a Berge-type minimax formula, but they leave open the question of a Gallai-Edmonds type structure theorem. This paper fills this gap by describing such a decomposition. We also prove that the vertex sets coverable by k-piece packings have a matroidal structure in a certain way.
Keywords:
Bibtex entry:
AUTHOR | = | {Janata, Marek and Loebl, Martin and Szab{\'o}, J{\'a}cint}, |
TITLE | = | {A Gallai-Edmonds type theorem for the $k$-piece packing problem}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2003}, |
NUMBER | = | {TR-2003-12} |