I单位圆盘图.docVIP

单位圆盘图 Brent N.CLARK and charles J.COLBOURN 加拿大N2L 3G1 安大略 滑铁卢 滑铁卢大学 计算机科学学院 David S.JOHNSON 回顾 1988.12.2 单位圆盘图是大少相同的圈组成的团的相交图：它们为广播网（手机网）和计算几何学中的一些问题提供一个图理论模型。我们证实了在单位圆盘图中很多标准图理论问题保留了NP完全的，包括染色、独立集、控制、独立控制和相关控制；控制问题的完备性被证明甚至对网格图、单位圆盘图的子类是成立的。相反的，当已知这个几何表示(在平面图中的圈)，我们给出一个找出团的多项式时间算法。 准备 考虑，在平面图上有n个大小相同的圈组成的一个集合。这些圈的相交图是一个有n个顶点的图，每一个顶点对应于一个圈，并且当两顶点相对应的圈相交(相接触的圈被认为是相交)时在这两个顶点之间有一条边。这样的图叫做单位圆盘图，并且有n个圈的这个集合是一个相交模型。相交图已经被广泛的研究(看[6]中例子)；对于很多类，针对标准图问题的有效算法已经被设计。先前被研究的相交族中很多形成了完美图类的子类，因为这个问题对于任意完美图都能有效地解决，所以许多有效的算法出现了。研究单位圆盘图，我们的动机之一是它们不需要是完美的；尤其，在任何长度为5或者更大的奇圈是一个单位圆盘图但不是完美的。类似的，尽管在平面上单位圆盘图可以用点有一个表示法，但它们不需要是二维平面的；尤其任意完全图是一个单位圆盘图。 研究单位圆盘图的第二个动机是它们出现在各种各样的背景中。下面是图理论的另一个定义。对于在平面上n个大小相同的圈形成了一个有n个顶点的图，这n个顶点对应于这n个圈，并且如果两个顶点对应的圈中有一个包含另外一个的中心，则它们之间连一条边。这是单位圆盘图的一个包含模型。一个纯粹的几何定义也是可用的。对于在平面上的n个点形成了一个有n个定点的图，这n个顶点与点相对应，并且两顶点之间有一条边时必须满足条件，当且仅当在这两个相应的点之间的欧几里德距离是不超过某个特殊的约束d。这就给了单位圆盘图的一个邻近模型。在相交和包含模型之间的变换是一个简单地加倍或者减半半径的问题。在相交与邻近模型之间的变换仅仅涉及了一个平面上圈中心的定义，这个圈有中心并且圈的直径是d。因此给出这三个模型中的任一个，我们都能在线性时间上得出另外两个。然而识别单位圆盘图的复杂程度是开的，建立这三个模型中的一个的复杂度也是一样的，虽然如此我们强烈怀疑这两个问题都是NP难的。 在固定模型中许多单位圆盘图潜在的应用出现了。如果我们设想每个点是一个发射/接收站，把发射台的有效广播范围当作一个圈。更近一步，如果每一个站点有相同的能量，这个圈的大小将几乎相同。广播网的这种模型在一定程度上是理想化的，因为它假设没有来自天气、物理障碍等干扰的产生。然而，这个模型被用在了关于广播网的重要问题的解决方法中[7,12,20];移动电话系统的出现已经通过这个模型的可用性分析了问题。参照中的两个例子是频率分配[7]和紧急发件人[18]。在这个频率分配问题中，分配不同的频率给发射台，这些发射台的范围相交。使用单位圆盘图的相交模型，我们看到频率分配(在它的最简单的形式里)是染色的。在紧急发件人问题中，找到发射台的一个最小集，它能(在一个紧急事件中)发射到所有剩余的站点。使用单位圆盘图的包含模型，这是控制。最后，一个利润的聚类问题是找到一个点的最大子集以至于没有两个点之间的距离超过d；用这个邻近模型，这是单位圆盘图中的一个最大团。 考虑到这些应用，我们研究单位圆盘图关于下列问题复杂性的限制的影响，我们知道一般图的NP完全：染色，团，独立集(点覆盖)，控制，独立控制和相关控制。我们也考虑对于网格图更进一步的限制的影响，这里网格图是一个单位圆盘图，在这个单位圆盘图中的所有交叉模型中，全部圆盘有带整数坐标和半径1/2的中心。正如表1总结的，我们知道关于这些限制，包括两个附加标准问题的完全性，这两个问题是圆盘图和网格图，它们的复杂度先前已经被解决。 这个论文的结果是被星号所标记的那些。对于团的案例，我们提出一个多项式时间算法，它将在被给一个图的相交(包含，邻近)模型时在单位圆盘图中找到一个最大的团。为了完全性的目的，我们也简单地描述了在表1中归属于[7,9,10]的结果的证明，因为这些参考主要地叙述了这些结果，并且以我们的知识是无法证明的。我们对来自于[10]的结果的证明也暗示了对于网格图这个先前开的独立控制集问题的NP完全性。 本论文的剩余部分被划分成了区域，一个问题一个部分。我们将要用前缀UD来详细说明在问题中单位圆盘图对问题的限制，用前缀GRID说明网格图的限制。当在所有首要的字母中一个问题的名字被给出，如在UD控制集中，我们指的是这个问题的决策问题的形式(例如，