×

The \(k\)-piece packing problem. (English) Zbl 1099.05066

Summary: 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 A. Kaneko [J. Comb. Theory, Ser. B 88, No. 2, 195–218 (2003; Zbl 1029.05125)], 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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 1029.05125
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, CR Acad Sci Paris Ser I Math 247 pp 258– (1958)
[2] Brewster, J Graph Theory 44 pp 81– (2003)
[3] Brewster, Information Processing Letters 86 pp 101– (2003)
[4] Cornuéjols, J Combin Theory Ser B 42 pp 285– (1988)
[5] Cornuéjols, J Combin Theory Ser B 40 pp 285– (1986)
[6] Cornuéjols, OR Letters 1 pp 139– (1982)
[7] Cornuéjols, Combinatorica 3 pp 35– (1983)
[8] Edmonds, Canad J Math 17 pp 449– (1965) · Zbl 0132.20903
[9] An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems, In: Proceedings of the fifteenth annual ACM symposium on theory of computing (15th STOC, Boston, MA, 1983), The Association for Computing Machinery, New York, (1983), 448–456.
[10] 1-restricted 2-matchings, manuscript, (2004).
[11] Hell, Electronic Notes in Discrete Math 5 pp 170– (2000)
[12] Hell, Colloquia Math Soc Bolyai 25 pp 273– (1978)
[13] Hell, SIAM J Computing 12 pp 601– (1983)
[14] Hell, Discrete Math 49 pp 118– (1984)
[15] Hell, SIAM J Algebraic Discrete Math 7 pp 113– (1986)
[16] Janata, KAM-DIMATIA series pp 638– (2003)
[17] Janata, Electronic J Combin 12 (2005)
[18] and , Generalized star packing problems, EGRES Technical Report TR-2004–17, www.cs.elte.hu/egres.
[19] Kaneko, J Combin Theory Ser B 88 pp 195– (2003)
[20] Kano, Discrete Math 283 pp 129– (2004)
[21] Kirkpatrick, Proc Tenth Annual ACM Symposium on Theory of Computing (STOC 1978) pp 240–
[22] Las Vergnas, Discrete Math 23 pp 241– (1978)
[23] Loebl, J Combin Theory Ser B 44 pp 338– (1988)
[24] Loebl, J Combin Theory Ser B 59 pp 106– (1993)
[25] Lovász, J Combin Theory 8 pp 391– (1970)
[26] Lovász, Annals of Discrete Mathematics 29 (1986)
[27] Tutte, J London Math Soc 22 pp 107– (1947)
[28] Tutte, Canad J Math 4 pp 314– (1952) · Zbl 0049.24202
[29] Wang, J Graph Theory 18 pp 161– (1994)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.