UNIT DISK GRAPHS
UNIT DISK GRAPHS
复制标题
DOI：
10.1016/0012-365x(90)90358-o
复制
发表时间：
1990-12-01
影响因子：
0.8
通讯作者：
JOHNSON, DS
中科院分区：
文献类型：
--
作者：
CLARK, BN;COLBOURN, CJ;JOHNSON, DS
单位圆盘图是平面上相等大小的圆的交图：它们为广播网络（蜂窝网络）和计算几何中的一些问题提供了图论模型。我们发现，许多标准的图论问题仍然是NP-完全的单位圆盘图，包括着色，独立集，支配，独立支配，连通支配; NP-完全的控制问题，甚至网格图，单位圆盘图的子类。相比之下，我们给出了一个多项式时间的算法来寻找集团时，提供的几何表示（圆在平面上）。
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.