The Edmonds-Gallai decomposition for the \(k\)-piece packing problem (Q1773199)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The Edmonds-Gallai decomposition for the \(k\)-piece packing problem |
scientific article; zbMATH DE number 2161309
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The Edmonds-Gallai decomposition for the \(k\)-piece packing problem |
scientific article; zbMATH DE number 2161309 |
Statements
The Edmonds-Gallai decomposition for the \(k\)-piece packing problem (English)
0 references
25 April 2005
0 references
A \(k\)-piece is a simple, connected graph with the highest degree exactly \(k\). The \(k\)-piece packing of a graph \(G\) is a subgraph \(P\) of \(G\) such that each connected component of \(P\) is a \(k\)-piece. In the paper, an Edmonds-Gallai type decomposition for maximal \(k\)-piece packings is given. Moreover, it is proved that the vertex sets coverable by \(k\)-piece packings have a certain matroidal structure.
0 references
barrier
0 references
galaxy
0 references
matching
0 references
matroid
0 references
