Article contents
A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
Published online by Cambridge University Press: 05 September 2011
Abstract
A unit disk graph is the intersection graphof a family of unit disks in the plane.If the disks do not overlap, it is also a unit coin graph or penny graph.It is known that finding a maximum independent setin 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 partitionin a penny graph is also NP-hard, and presenttwo linear-time approximation algorithms for the computation of clique partitions:a 3-approximation algorithm for unit disk graphsand a 2-approximation algorithm for penny graphs.
Keywords
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2011
References
- 9
- Cited by