Name
Abstract | ||
|---|---|---|
Generalizing Kaneko's long path packing problem, Hartvigsen, Hell and Szabo 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. |
Year | Venue | DocType |
|---|---|---|
2005 | ELECTRONIC JOURNAL OF COMBINATORICS | Journal |
Volume | Issue | ISSN |
12.0 | 1.0 | 1077-8926 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marek Janata | 1 | 3 | 1.48 |
| Martin Loebl | 2 | 152 | 28.66 |
| Jácint Szabó | 3 | 113 | 12.67 |