The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
type: Item
instance of: scholarly article
title: The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
zbMATH Open document ID: 1062.05119
author: Marek Janata
author: Martin Loebl
author: Jácint Szabó
published in: The Electronic Journal of Combinatorics
publication date: 2005-04-25T00:00:00Z
full work available at URL: https://eudml.org/doc/124598
full work available at URL: v12i1r8.html
review text: 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.
reviewed by: Martin Knor
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 2161309
zbMATH Keywords: barrier
zbMATH Keywords: galaxy
zbMATH Keywords: matching
zbMATH Keywords: matroid
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2161309