Networks · 1995 · 494 citations · 21 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsGeometryGeometric OptimizationGraph AlgorithmsGraph ColoringGraph TheoryHeuristic OptimizationHeuristic SearchDisk GraphsDominating SetsIndependent Set AlgorithmsIntersectionIntersection GraphsMaximum Independent Set ApproximationUnit Disk GraphsVertex Cover Approximation
Abstract 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.
21
Sphere Packings, Lattices and Groups.
H. S. M. Coxeter, J. H. Conway, N. J. A. Sloane · American Mathematical Monthly · 1989 · 3.5K citations
Brent N. Clark, Charles J. Colbourn, David Johnson · Discrete Mathematics · 1990 · 1.4K citations
Frequency assignment: Theory and applications
William K. Hale · Proceedings of the IEEE · 1980 · 1.3K citations