Premium
The k ‐piece packing problem
Author(s) -
Hartvigsen David,
Hell Pavol,
Szabó Jácint
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20161
Subject(s) - mathematics , combinatorics , disjoint sets , graph , degree (music) , discrete mathematics , matching (statistics) , time complexity , statistics , physics , acoustics
A k ‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k . We consider the problem of covering the maximum number of nodes of a graph by node disjoint k ‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [19[, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory