On Coloring Unit Disk Graphs |
| |
Authors: | A. Gräf M. Stumpf G. Weißenfels |
| |
Affiliation: | Johannes Gutenberg-Universit?t, Musikwissenschaftliches Institut, Abteilung Musikinformatik, P.O. Box 3980, 55099 Mainz, Germany. {ag,martin,wf}@muwiinfa.geschichte.uni-mainz.de., DE
|
| |
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. Received February 12, 1996; revised October 9, 1996. |
| |
Keywords: | . Channel assignment problem Graph coloring Unit disk graphs Approximation algorithm. |
本文献已被 SpringerLink 等数据库收录! |
|