Voir la notice de l'article provenant de la source Numdam
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.
@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},
publisher = {EDP-Sciences},
volume = {45},
number = {3},
year = {2011},
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 :