Geodesic
The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
The electronic journal of combinatorics, Tome 12 (2005)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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

Cité par Sources :