×

On minimum clique partition and maximum independent sets on unit disk graphs and penny graphs: complexity and approximation. (English) Zbl 1075.05571

Liebling, T. (ed.) et al., Latin-American conference on combinatorics, graphs and applications. Papers from the conference, Santiago, Chile, August 16–20, 2004. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 18, 73-79 (2004).
For the entire collection see [Zbl 1074.05004].

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: Link

References:

[1] Baker, B. S.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 41, No. 1, 153-180 (1994) · Zbl 0807.68067
[2] H. Breu, ”Algorithmic Aspects of Constrained Unit Disk Graphs”, PhD. Thesis, University of British Columbia, 1996
[3] Breu, H.; Kirkpatrick, D. G.: Unit disk graph recognition is NP-hard. Computational geometry 9, 3-24 (1998) · Zbl 0894.68099
[4] Clark, B. N.; Colbourn, C. J.; Johnson, D. S.: Unit disk graphs. Discrete mathematics 86, 165-177 (1990) · Zbl 0739.05079
[5] T. Erlebach, K. Jansen and E. Seidel, Polynomial-time approximation schemes for geometric graphs, in ”Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms”, 2001, pp. 671 – 679 · Zbl 0988.65020
[6] Garey, M. R.; Johnson, D. S.: The rectilinear Steiner tree problem is NP-complete. SIAM journal of applied mathematics 32, 826-834 (1977) · Zbl 0396.05009
[7] Garey, M. R.; Johnson, D. S.: Computers and intractability: A guide to the theory of NP-completeness. (1979) · Zbl 0411.68039
[8] Golumbic, M. C.: Algorithmic graph theory and perfect graphs. (1980) · Zbl 0541.05054
[9] Iii, H. B. Hunt; Marathe, M. V.; Radhakrishnan, V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of algorithms 26, 238-274 (1998) · Zbl 0894.68105
[10] Marathe, M. V.; Breu, H.; Iii, H. B. Hunt; Ravi, S. S.; Rosenkrantz, D. J.: Simple heuristics for unit disk graphs. Networks 25, 59-68 (1995) · Zbl 0821.90128
[11] Matsui, T.: Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. Lecture notes in computer science 1763, 194-200 (2000) · Zbl 0955.05100
[12] Valiant, L. G.: Universality considerations in VLSI circuits. IEEE transactions on computers 30, 135-140 (1981) · Zbl 0455.94046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.