Geodesic
The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
The electronic journal of combinatorics, Tome 12 (2005)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
Generalizing Kaneko's long path packing problem, Hartvigsen, Hell and Szabó 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 in the case $k=1$ we get the classical matching problem. They give a polynomial algorithm, a Tutte-type characterization and a Berge-type minimax formula for the $k$-piece packing problem. However, they leave open the question of an Edmonds-Gallai type decomposition. This paper fills this gap by describing such a decomposition. We also prove that the vertex sets coverable by $k$-piece packings have a certain matroidal structure.
DOI : 10.37236/1905
Classification : 05C70
Mots-clés : barrier, galaxy, matching, matroid 
Marek Janata; Martin Loebl; Jácint Szabó. The Edmonds-Gallai decomposition for the \(k\)-piece packing problem. The electronic journal of combinatorics, Tome 12 (2005). doi: 10.37236/1905
@article{10_37236_1905,
     author = {Marek Janata and Martin Loebl and J\'acint Szab\'o},
     title = {The {Edmonds-Gallai} decomposition for the \(k\)-piece packing problem},
     journal = {The electronic journal of combinatorics},
     year = {2005},
     volume = {12},
     doi = {10.37236/1905},
     zbl = {1062.05119},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1905/}
}
TY  - JOUR
AU  - Marek Janata
AU  - Martin Loebl
AU  - Jácint Szabó
TI  - The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
JO  - The electronic journal of combinatorics
PY  - 2005
VL  - 12
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1905/
DO  - 10.37236/1905
ID  - 10_37236_1905
ER  - 
%0 Journal Article
%A Marek Janata
%A Martin Loebl
%A Jácint Szabó
%T The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
%J The electronic journal of combinatorics
%D 2005
%V 12
%U http://geodesic.mathdoc.fr/articles/10.37236/1905/
%R 10.37236/1905
%F 10_37236_1905

Cité par Sources :