The complexity of generalized clique packing |
| |
| Authors: | DG Corneil |
| |
| Institution: | Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4, Canada |
| |
| Abstract: | The Ki - j packing problem Pi, j is defined as follows: Given a graph G and integer k does there exist a set of at least kKi's in G such that no two of these Ki's intersect in more than j nodes. This problem includes such problems as matching, vertex partitioning into complete subgraphs and edge partitioning into complete subgraphs. In this paper it is shown thhat for i ? 3 and 0?j?i ?2 the Pi, j problems is NP-complete. Furthermore, the problems remains NP-complete for i?3 and 1?j?i ?2 for chordal graphs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
