Simple heuristics for unit disk graphs. (English) Zbl 0821.90128

Marathe, M. V.; Breu, H.; Hunt, H. B. III; Ravi, S. S.; Rosenkrantz, D. J.

Networks 25, No. 2, 59-68 (1995).

Summary: Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring, and minimum dominating set. We also present an on-line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and intersection graphs of higher-dimensional regular objects.

MSC:

90C35	Programming involving graphs or networks
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

unit disk graphs; maximum independent set; minimum vertex cover; minimum coloring; minimum dominating set; on-line coloring heuristic

References:

[1]	, , , and , Proof verification and hardness of approximation problems. Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS 1992), Pittsburgh, PA (Oct. 1992) 14–23. · Zbl 0977.68539
[2]	Approximation algorithms for NP-complete problems on planar graphs. Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983), Tucson, AZ (Nov. 1983) 265–273.
[3]	J. ACM 41 pp 155– (1994)
[4]	and , On approximating a vertex cover for planar graphs. Proceedings of the 14th Annual ACM Symposium on Theory of Computing (May 1982) 303–309.
[5]	and , A local ratio theorem for approximating the weighted vertex cover problem. Analysis and Design of Algorithms for Combinatorial Problems. Annals of Discrete Mathematics, Vol. 25 North-Holland, New York. (1985) 27–45. · doi:10.1016/S0304-0208(08)73101-3
[6]	and , Unit disk graph recognition is NP-hard. Technical Report 93–27, Department of Computer Science, University of British Columbia (Aug. 1993).
[7]	Clark, Discr. Math. 86 pp 165– (1990)
[8]	and , Sphere packings, Lattices and Groups. Springer-Verlag. New York (1988). · doi:10.1007/978-1-4757-2016-7
[9]	and , Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, CA (1979). · Zbl 0411.68039
[10]	Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). · Zbl 0541.05054
[11]	Gyarfas, J. Graph Theory 12 pp 217– (1988)
[12]	Hale, Proc. IEEE 68 pp 1497– (1980)
[13]	Hochbaum, Discr. Appl. Math. 6 pp 243– (1983)
[14]	Hochbaum, J. ACM 32 pp 130– (1985)
[15]	, , , , and , A unified approach to approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Proceedings of the Second Annual European Symposium on Algorithms (ESA’94) (Sept. 1994).
[16]	Irving, Inf. Proc. Lett. 37 pp 197– (1991)
[17]	Coloring inductive graphs on-line. Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS) (Oct. 1990) 470–479.
[18]	Johnson, JCSS 9 pp 256– (1974)
[19]	Kammerlander, IEEE Trans. Select. Areas Commun. 2 pp 589– (1984)
[20]	Polynomially bounded minimization problems which are hard to approximate. Proceedings of the 20th ICALP. Lecture Notes in CS Vol. 700, Sweden (July 1993) 52–63.
[21]	Kierstead, Discr. Math. 88 pp 231– (1991)
[22]	Kierstead, Congress. Numer. 33 pp 143– (1981)
[23]	and , On the hardness of approximating minimization problems. Proceedings of the 25th ACM Symposium on Theory of Computing(STOC 1993), San Diego, CA (May 1993) 286–293. · Zbl 1310.68094
[24]	, and , Efficient approximation algorithms for domatic partition and online coloring of circular-arc graphs. Proceedings of the International Conference on Computing and Information (ICCI 93), Sudbury, Canada (May 1993) 26–30.
[25]	Nemhauser, Math. Program. 8 pp 232– (1975)
[26]	Graph Theory and Its Applications to Problems of Society. SIAM. Philadelphia, 1978. · doi:10.1137/1.9781611970401
[27]	A coloring algorithm for interval graphs. Proceedings 1987 MFCS. Lecture Notes in CS, Vol. 379, Springer-Verlag, New York (1987) 471–480. · Zbl 0755.68112
[28]	Optimal on-line coloring of circular arc graphs. Private communication (March 1994).
[29]	Three-dimensional Geometry & Topology. The Geometry Center, University of Minnesota, Minneapolis (1991).
[30]	Wilson, IEEE Trans. Select. Areas in Commun. 2 pp 507– (1984)
[31]	Wong, Inf. Proc. Lett. 28 pp 281– (1988)