ON COLORING UNIT DISK GRAPHS

Authors
GRAF A STUMPF M WEISSENFELS G
Citation
A. Graf et al., ON COLORING UNIT DISK GRAPHS, Algorithmica, 20(3), 1998, pp. 277-293
Citations number
18
Categorie Soggetti
Mathematics,"Computer Science Software Graphycs Programming",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
20
Issue
3
Year of publication
1998
Pages
277 - 293
Database
ISI
SICI code
0178-4617(1998)20:3<277:>2.0.ZU;2-E
Abstract
In this paper the coloring problem for unit disk (LTD) graphs is consi dered. UD graphs are the intersection graphs of equal-sized disks in t he plane. Colorings of UD graphs arise in the study of channel assignm ent 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 greater than or equal to 3. Furthermore, a new 3-approximation algorithm for the problem is prese nted which is based on network flow and matching techniques.