On coloring unit disk graphs

被引：72

作者：

Graf, A ^{[1
]}

Stumpf, M ^{[1
]}

Weissenfels, G ^{[1
]}

机构：

[1] Johannes Gutenberg Univ Mainz, Musikwissensch Inst, Abt Musikininformat, D-55099 Mainz, Germany

来源：

ALGORITHMICA | 1998年 / 20卷 / 03期

关键词：

channel assignment problem; graph coloring; unit disk graphs; approximation algorithm;

D O I：

10.1007/PL00009196

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this paper the coloring problem for unit disk (LTD) 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 greater than or equal to 3. Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.

引用

页码：277 / 293

页数：17

共 18 条

[1]

BREU H, 1993, 9327 U BRIT COL DEP

[2] UNIT DISK GRAPHS [J].

CLARK, BN ;

COLBOURN, CJ ;

JOHNSON, DS .

DISCRETE MATHEMATICS, 1990, 86 (1-3) :165-177

[3]

Even S., 1979, Graph Algorithms

[4]

Ford L. R, 1962, FLOWS NETWORKS

[5]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[6]

Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs

[7]

GRAF A, 1994, 1794 J GUTENBERG U

[8]

GRAF A, 1995, THESIS J GUTENBERG U

[9]

GRAF A, 1992, 592 J GUTENBERG U

[10] FREQUENCY ASSIGNMENT - THEORY AND APPLICATIONS [J].

HALE, WK .

PROCEEDINGS OF THE IEEE, 1980, 68 (12) :1497-1514

← 1 2 →