| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420588 | Discrete Applied Mathematics | 2008 | 9 Pages |
Abstract
Given a graph G=(V,E)G=(V,E) and a positive integer kk, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of VV into kk disjoint subsets V1,V2,…,VkV1,V2,…,Vk such that the subgraph induced by each part ViVi is a complete subgraph (clique) of GG. In this paper, we establish both the NP-completeness of pic for planar cubic graphs and the Max SNP-hardness of pic for cubic graphs. We present a deterministic polynomial time 54-approximation algorithm for finding clique partitions in maximum degree three graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
M.R. Cerioli, L. Faria, T.O. Ferreira, C.A.J. Martinhon, F. Protti, B. Reed,