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.
Mots clés : 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},
publisher = {EDP-Sciences},
volume = {45},
number = {3},
year = {2011},
doi = {10.1051/ita/2011106},
mrnumber = {2836493},
zbl = {1228.05224},
language = {en},
url = {http://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ita/2011106/
[1] , Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41 (1994) 153-180. | MR | Zbl
[2] , and , Approximation hardness and satisfiability of bounded occurrence instances of SAT, in Electronic Colloquium on Computational Complexity - ECCC (2003).
[3] , Algorithmic Aspects of Constrained Unit Disk Graphs. Ph.D. thesis, University of British Columbia (1996).
[4] and , Unit disk graph recognition is NP-hard. Computational Geometry 9 (1998) 3-24. | MR | Zbl
[5] , , and , On sum coloring and sum multi-coloring for restricted families of graphs. Manuscript available at http://www.cs.toronto.edu/~bor/2420f10/stacs.pdf consulted 30 July 2011. | MR | Zbl
[6] , and , Unit disk graphs. Discrete Math. 86 (1990) 165-177. | MR | Zbl
[7] , , and , On minimum clique partition and maximum independent set in unit disk graphs and penny graphs: complexity and approximation. LACGA'2004 - Latin-American Conference on Combinatorics, Graphs and Applications. Santiago, Chile (2004). Electron. Notes Discrete Math. 18 (2004) 73-79. | MR | Zbl
[8] , and , Polynomial-time approximation schemes for geometric graphs, in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (2000) 671-679. | MR | Zbl
[9] , On some problems of elementary and combinatorial geometry. Ann. Math. Pura Appl. Ser. 103 (1975) 99-108. | MR | Zbl
[10] , Planar formulae and their uses. SIAM J. Comput. 43 (1982) 329-393. | MR | Zbl
[11] and , The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32 (1977) 826-834. | MR | Zbl
[12] and , Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, New York (1979). | MR | Zbl
[13] , The complexity of comparability graph recognition and coloring. Computing 18 (1977) 199-208. | MR | Zbl
[14] , Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). | MR | Zbl
[15] , Lösung zu problem 664a. Elem. Math. 29 (1974) 14-15. | MR
[16] , , , , and , NC-Approximation schemes for NP- and PSPACE-Hard problems for geometric graphs. J. Algor. 26 (1998) 238-274. | MR | Zbl
[17] and , The minimum broadcast time problem for several processor networks. Theor. Comput. Sci. 147 (1995) 69-85. | MR | Zbl
[18] , , , and , Simple heuristics for unit disk Graphs. Networks 25 (1995) 59-68. | MR | Zbl
[19] , Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In Discrete and Computational Geometry. Lect. Notes Comput. Sci. 1763 (2000) 194-200. | MR | Zbl
[20] and , A weakly robust PTAS for minimum clique partition in unit disk graphs (Extended Abstract), Proceedings of SWAT 2010. Lect. Notes Comput. Sci. 6139 (2010) 188-199. | MR | Zbl
[21] and , Good quality virtual realization of unit ball graphs, Proceedings of the 15th Annual European Symposium on Algorithms. Lect. Notes Comput. Sci. 4698 (2007) 311-322. | Zbl
[22] , Problem 664a. Elem. Math. 27 (1972) 19.
[23] , Efficient Graph Representations, Fields Institute Monographs 19. American Mathematical Society (2003). | MR | Zbl
[24] , Universality considerations in VLSI circuits. IEEE Trans. Comput. 30 (1981) 135-140. | MR | Zbl
Cité par Sources :
