zbMATH — the first resource for mathematics

Packings by cliques and by finite families of graphs. (English) Zbl 0582.05046
If F is a family of connected graphs and G is a graph, then an F-packing of G is a subgraph of G each component of which belongs to F. This paper contains a polynomially bounded algorithm for finding an F-packing of G which as many vertices as possible when F contains $$K_ 2$$ and all other graphs in F are hypomatchable, i.e., the deletion of any vertex leaves a graph with a perfect matching. If F does not contain $$K_ 2$$, then the problem of finding an F-packing with as many vertices as possible is often NP-complete. This is shown to be the case when F consists of complete graphs of order at least 3 or when F consists of cycles of length at least 6.

MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C35 Extremal problems in graph theory 68R10 Graph theory (including graph drawing) in computer science
Full Text:
References:
 [1] Berge, C, Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029 [2] Bondy, J.A; Murty, U.S.R, Graph theory with applications, (1976), American Elsevier New York · Zbl 1134.05001 [3] Cornuejols, G; Pulleyblank, W, A matching problem with side conditions, Discrete math., 29, 135-159, (1980) · Zbl 0446.05031 [4] Cunningham, W.H; Marsh, A.B, A primal algorithm for optimum matching, Math. programming study, 8, 50-72, (1978) · Zbl 0409.90081 [5] Edmonds, J, Paths, trees, and flowers, Canad. J. math., 17, 449-467, (1965) · Zbl 0132.20903 [6] Edmonds, J, Maximum matching and a polyhedron with (0, 1) vertices, J. res. nat. bureau of standards, 69B, 125-130, (1965) · Zbl 0141.21802 [7] Edmonds, J; Johnson, E.L, Matching: a well-solved class of integer linear programs, (), 89-92 [8] Garey, M.R; Johnson, D.S, Computers and intractability, (1979), Freeman San Francisco · Zbl 0411.68039 [9] Hell, P; Kirkpatrick, D.G, Scheduling, matching, and coloring, (), 272-280, Algebraic Methods in Graph Theory, Szeged (Hungary) · Zbl 0474.05054 [10] Hell, P; Kirkpatrick, D.G, On generalized matching problems, Inform. process. letters, 12, 33-35, (1981) · Zbl 0454.68077 [11] P. Hell and D.G. Kirkpatrick, Packings by complete bipartite graphs, submitted to SIAM J. Algebraic Discrete Methods. · Zbl 0597.05050 [12] P. Hell and D.G. Kirkpatrick, (g, f)-factors and packings—characterizations and algorithms, TR 83-6. Computer Science Department, University of B.C. [13] Kirkpatrick, D.G; Hell, P, On the completeness of a generalized matching problem, (), 240-245 · Zbl 1282.68182 [14] Kirkpatrick, D.G; Hell, P, On the complexity of general graph factor problems, SIAM J. computing, 12, 601-609, (1983) · Zbl 0525.68023 [15] Kuhn, H.W, The Hungarian method for the assignment problem, Naval res. logist. quart., 2, 83-97, (1955) · Zbl 0143.41905 [16] Lawler, E.L, Combinatorial optimization, (1976), Holt, Rinehart, and Winston New York · Zbl 0362.90076 [17] Lovász, L, Combinatorial problems and exercises, (1979), North-Holland Amsterdam · Zbl 0439.05001 [18] Tutte, W.T, The factorisation of linear graphs, J. London math. soc., 22, 107-111, (1947) · Zbl 0029.23301 [19] Vornberger, O, Komplexität von wegeproblemen in graphen, Reihe teoretische informatik, 5, (1979), Universität Paderborn · Zbl 0461.05041 [20] Cornuejols, G; Hartvigsen, D; Pulleyblank, W, Packing subgraphs in a graph, Operations research letters, 4, 139-143, (Sept. 1982)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.