Abstract.
In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received February 12, 1996; revised October 9, 1996.
Rights and permissions
About this article
Cite this article
Gräf, A., Stumpf, M. & Weißenfels, G. On Coloring Unit Disk Graphs . Algorithmica 20, 277–293 (1998). https://doi.org/10.1007/PL00009196
Issue Date:
DOI: https://doi.org/10.1007/PL00009196