Geodesic
A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 3, pp. 331-346 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

A unit disk graph is the intersection graph of 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 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 3-approximation algorithm for unit disk graphs and a 2-approximation algorithm for penny graphs.

DOI : 10.1051/ita/2011106
Classification : 05C69, 05C75, 68W25, 68Q25
Keywords: unit disk graphs, unit coin graphs, penny graphs, independent set, clique partition, approximation algorithms 
@article{ITA_2011__45_3_331_0,
     author = {Cerioli, Marcia R. and Faria, Luerbio and Ferreira, Talita O. and Protti, F\'abio},
     title = {A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {331--346},
     year = {2011},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {3},
     doi = {10.1051/ita/2011106},
     mrnumber = {2836493},
     zbl = {1228.05224},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2011106/}
}
TY  - JOUR
AU  - Cerioli, Marcia R.
AU  - Faria, Luerbio
AU  - Ferreira, Talita O.
AU  - Protti, Fábio
TI  - A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2011
SP  - 331
EP  - 346
VL  - 45
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2011106/
DO  - 10.1051/ita/2011106
LA  - en
ID  - ITA_2011__45_3_331_0
ER  - 
%0 Journal Article
%A Cerioli, Marcia R.
%A Faria, Luerbio
%A Ferreira, Talita O.
%A Protti, Fábio
%T A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2011
%P 331-346
%V 45
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2011106/
%R 10.1051/ita/2011106
%G en
%F ITA_2011__45_3_331_0
Cerioli, Marcia R.; Faria, Luerbio; Ferreira, Talita O.; Protti, Fábio. A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 3, pp. 331-346. doi: 10.1051/ita/2011106

Cité par Sources :