|
|||||
|
|
Partition into cliques for cubic graphs: Planar case, complexity and approximation |
|
| Authors: | MR Cerioli L Faria B Reed |
| Institution: | a IM - UFRJ, Rio de Janeiro, Brazil b COPPE - UFRJ, Rio de Janeiro, Brazil c DMAT, FFP - UERJ, Rio de Janeiro, Brazil d IC - UFF, Rio de Janeiro, Brazil e NCE - UFRJ, Caixa Postal 2324, 20001-970, Rio de Janeiro, Rj, Brazil f School of Computer Science, McGill University, Montreal, Quebec, Canada |
| Abstract: | Given a graph G=(V,E) and a positive integer k, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of V into k disjoint subsets V1,V2,…,Vk such that the subgraph induced by each part Vi is a complete subgraph (clique) of G. 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  -approximation algorithm for finding clique partitions in maximum degree three graphs. |
| Keywords: | NP-complete Max SNP-hard Partition into cliques Coloring Approximation Cubic planar graphs |
| 本文献已被 ScienceDirect 等数据库收录！ | |