UNIT DISK GRAPHS

被引：882

作者：

CLARK, BN ^{[1
]}

COLBOURN, CJ ^{[1
]}

JOHNSON, DS ^{[1
]}

机构：

[1] AT&T BELL LABS, MURRAY HILL, NJ 07974 USA

来源：

DISCRETE MATHEMATICS | 1990年 / 86卷 / 1-3期

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1016/0012-365X(90)90358-O

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Unit disk graphs are the intersection graphs of equal sized circles in the plane: they provide a graph-theoretic model for broadcast networks (cellular networks) and for some problems in computational geometry. We show that many standard graph theoretic problems remain NP-complete on unit disk graphs, including coloring, independent set, domination, independent domination, and connected domination; NP-completeness for the domination problem is shown to hold even for grid graphs, a subclass of unit disk graphs. In contrast, we give a polynomial time algorithm for finding cliques when the geometric representation (circles in the plane) is provided.

引用

页码：165 / 177

页数：13

共 20 条

[1]

CLARK BN, 1985, THESIS U WATERLOO

[2] THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS [J].