A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
Marcia R. Cerioli, Luerbio Faria, Talita O. Ferreira, Fábio Protti (2011)
RAIRO - Theoretical Informatics and Applications
Similarity:
A is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a or . It is known that finding a maximum independent set in a unit disk graph is a NP-hard problem. In this work we extend this result to penny graphs. Furthermore, we prove that finding a minimum clique partition in a penny graph is also NP-hard, and present two linear-time approximation algorithms for the computation of clique partitions: a -approximation algorithm for unit...