TR-2003-12

A Gallai-Edmonds type theorem for the k-piece packing problem

Marek Janata, Martin Loebl, Jácint Szabó

Published in:
Electron. J. Combin. 12 (2005) 1



Abstract

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:
Graph packing, Gallai-Edmonds decomposition, Matroid


Bibtex entry:

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


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