英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

---

二维网格布局问题的精确解

摘要

给出一个无定向图G = (V,E), 我们考虑其顶点的注入映射到k维笛卡儿整数网格。 在这样的嵌入中，我们对那些最小化所得到的边缘长度的总和的那些感兴趣，其中由量定义。情况k = 1是众所周知的最小线性排列问题。我们证明，对于任何固定的网格维度，一般问题是NP-hard。 我们的计算研究集中在k = 2的情况下，作为第一个精确优化算法，我们提出了稀疏图的分支方案。 引入并分析了几类有效不等式，以分析两个相应多面体的面定义属性。 最后，提出了德国癌症研究中心（DKFZ）在问题成功实际应用中的计算结果。

关键词：几何嵌入、二维网格布局、多面体组合

1 简介

最小线性规划问题是一个经典的组合优化问题，它由一个无向图发现的Phi;对V在 { 1，hellip;，| V | }上一对一映射，使得尽可能小。映射phi;也可以被理解为嵌入G的顶点在区间[ 1，| V | ] 的整数关口。这个问题可以推广到k维（网格）安排问题（k-GAP）上，如果顶点不映射在曲线上但在k维笛卡尔整数网格,。我们用g（）表示这个网格。我们现在以曼哈顿或对电网的两个端节点之间的距离作为一个边缘的长度。

在一般情况下，对一维版本的模型和算法不容易适应，因为他们是基于概念的置换 、 顺序”、“标记”或“中间态”。此外，有些问题可以很简单的回答为K = 1是更复杂的高维问题。一个例子是必要的网格大小的问题，以允许最佳的嵌入。凡为K = 1网格显然是不够的，在更高维度的网格需要提供比顶点的数目更多的网格点。显然，栅极一直是大到足以包含最优解。然而，仍将是空的。对于k = 2，我们可以发现，是最小的正方形网格的大小，所有的图形| V |顶点可以优化嵌入式[ 1 ]。

应用程序使用的实例，它已被优化的嵌入式图形倾向于保护当地的拓扑结构，即通过减少边缘的长度，相邻的顶点被放置在靠近彼此。我们将在第6.3节中讨论一个这样的应用。这个问题的NP-hardness因k=1而知名（如约翰逊等人所示）。我们将在2节中证明的问题仍然是NP-hard的k的任何固定选择的问题。汉森介绍了间隙为k维几何嵌入问题的特殊情况而不为其指定一个不同的名字。他也是第一个给出一个图嵌入在一个提供了多项式时间算法的事实或最优性的人。埃文等人采用被称为扩展的度量方法一般分枝定界技术显著提高这种近似结果。最近，由Charikar等人通过对问题的递归细分根据最优均衡削减，这必将进一步提高到。

图 1 1到3维的立方体格子

2011年德曼等人[6]提出了一种在二维网格上嵌入完整图的动态规划方法，它智能地利用对称性特征和宽度-高度关系的最佳嵌入的情况下，解决多达80个顶点的问题实例。但是，这些考虑仅在图表完整是有效的。精确解方法既不研究非完整的图形，也没有考虑在多维的情况下的问题。

我们给出了一般图上二维问题的第一个精确分支和切割方案。它可以很容易地扩展到更高的维度。第3节介绍IP模型，其次第4节是一种有效不等式最重要的课。在第5节他们中的一些将被示出定义的刻面对应多面体。在第6节中分支和切割算法得到解决。我们的结论与实际应用的计算结果在第6.3节的文件中。

2计算复杂性

目前，一般的复杂性的结果是已知的K = 1情况下。约翰逊等[ 2 ]证明一般图的NP-hardness，Even和Shiloach [7 ]证明了它的双相性问题。一般的问题k-GAP为G，例如结构简单多项式时间内可解，如果G是一个路径，周期或星形图（见第4节）。如果G是一个完全图Kn，有算法来计算最佳嵌入在 [6]。然而，对于一般的图k-GAP复杂性和固定尺寸的尚未确定。

在本节中，我们证明了k-GAP是对于任何固定的 NP。对于，这个结果甚至是平面图中的每个顶点至多有3个邻居。所用的证明方法是不同于Garey和Johnson的相关证据，包括从构造分配问题转化。

2.1决策问题与转化

我们需要证明下面的决策问题是NP完全问题的一类成员.

定义1（k-GDAP）：给定一个无向图，固定尺寸的、网格和一个整数h，是否有一个嵌入这样的?

这个问题显然是NP，通俗地说，是正确的，一个是“是”回答可以检查在多项式时间内通过总结积分边长度和比较结果S。为了显示其成员在NPC，我们随后提供了一个转型的分区问题：

定义2（PD）：对于一个给定的正整数多重集是否有一个分区为两个子集和，使得？

卡普[ 8 ]证明了PD的NP完全性。在我们说明转换算法之前，需要引入两个定义。一组积分点以如下方式诱导图。为每个点引入一个顶点，然后在这些对应的积分点之间有1个顶点的边。

定义3：给定一个有限点集和图，如果存在一个双射使得，我们说G是由Z引起的。

定义4：如果一个图是由k栅极引起的，那么这个图被称为k维立方体阶梯的长度。

图1中描绘了一些立方体梯子。我们假设是本节其余部分偶数。否则，相应的PD实例都回答“不”。对于每一个固定的维、下列算法将PD的实例在多项式时间k-GADP实例。

算法1：输入：。输出：G，g，h。

1，初始化G的k维栅极。

2，对于S中的每个元素，构造一个长度为的长度的（kminus;1）维立方体梯形图网络。

3，用下述方式构造一个)的图：从G的点删除为，，设置指向被剩余点集合的诱导图（见图2）。

4，令 。

5，将h设置为G的边数。

图 2 算法一示意图

这种转换的思想从图2中清楚可见。在我们的本地替换策略，我们用一个立方体取代每个整数SI。这些可以被嵌入在G中，使得每个边缘具有长度1，当且仅当数字SI可以被划分成两组相等的款项时成立。

定义5：是说对于一维可插入的g如果有一个嵌入，使得对于所有都成立。

2.2 复杂的结果

定理1：2-GAP是最大顶点度3的NP-hard的平面图。k-GAP是对于图G中任何固定的的NP-hard，其中每个顶点最多有K 1邻域。证明这个定理，我们不得不首先考虑嵌入性性质的立方体。

备注1：对于k维单位立方体及其骨架图有下列要求要遵循：

1. 作为一个多面体的面（Kminus;1）维立方体。
2. IK的定点恰恰是向量，所有方面可写为或对于一个分别的。
3. 如果F是IK的一个方面，那么正好一半的顶点位于F内。其余的顶点位于IK的一个共同的刻面H，称为F对立面。
4. 给定一个面F和其对立面H，是F和H的顶点之间的双射：。

证明：（1）和（2）是已知的。（3）一个面上的所有顶点集合是集合或对于i = 1,hellip;,K。显然，面上其他剩余的顶点或。 （4）如果位于F =，则，和是唯一的顶点都位于对立面且跟U距离1。

备注2：让表示一个单位立方体的骨架图，则对与上所有一维可插入点两两一致。

证明：对于k = 1，恒成立。现在假设。我们将表明，它也适用于，备注1的（1）和（3），可以分成的两个部分、，顶点导出图G（）和G（）都是同构的。通过归纳假设，G（）必须嵌入在2times;···times;2子网格。W.l.o.g.，让这个子网格是。对于每个是相邻的一个根据注1的（4），要么对于所有或对于所有。w.l.o.g.假设第二种情况。现在每一个与对于会导致边缘(v,u)将超过1，其中U是注1（4）中被定义的对立点。因此，这两个和需要被嵌入在（K 1）维G（2,hellip;,2）平面内。

从证明中我们可以看到：

推论1：如果一个F的单位立方体的顶点固定在 等所有边e（F）上的长度是1，那么只有一个映射的其余顶点V（） F对剩下的网格点，所有边缘长度1。

从推论1和备注2我们得到：推论2：在一个立方体上嵌入成对一致

定理1的证明：从推论2，算法1图是G上唯一一维可插入的空点，给出了这样一个嵌入，导致两（Kminus;1）维立方体的梯子的长度为S和的一半。由此可见，()是PD的一个不错的实例，当且仅当相应的立方体图是一这些剩下的维可插入嵌入网格点时成立。

3 整数规划模型

我们引入一个配方的二维间隙作为一个整数规划问题。它可以很容易地推广到更高的维度。我们使用的积分距离变量每个无序对的顶点网格给u和v之间的L1距离。距离变量的使用是由刘和Vannelli提出了计算最小线性排列问题的下界。我们按照二维间隙类似的方法，但延长下限的计算方法进行了完整的IP配方。

我们的模型是基于所谓的嵌入性约束。我们不能直接在d变量处制定，我们编码与二进制变量。我们定义 = 1如果端节点u和v边E有距离和 = 0则。因此，我们的关系 ，那里是一个上限的最大距离。请注意，每个在d变量处的约束可以在X变量处重新制定。

现在我们可以定义嵌入约束。对一个图表示E = {}。如果我们有积分距离与有关，我们称为G的距离向量，如果H是G的一个子图，那么表示距离向量d限于H边上

定义6：设由距离矢量d与栅格或给予。(G,d)说是G可插入的，如果有一个嵌入phi;：V→G 对于所有的成立。

定义7：对于图和距离向量D不等式 被称为G和d可嵌入性约束。

作为一个例子，考虑K3（3节点的完全图）和 = 3。这个图不是对于任何二维网格G的距离矢量成立的可插入G。因此，嵌入性约束是错误的。请注意，这个约束满足所有其他距离矢量。

对于一个给定的最大边长 的IP模型可表示如下：

所有的子图使得不是嵌入，

，;

,

值总是可以被选为网格的径对角。条件（2）和（3）定义变量X。目标函数使得V嵌入边缘总长度最小，对于任何非嵌入约束条件（1）的切断所有的变量分配的距离等价于所有。在这种情况下，不等式（1）被违反，因为。然而，它满足所有其他距离矢量。即假设为边。然后，从而满足不等式。

有几个优点，这种模式相比，一个简单的位置变量模型，二进制变量指示是否V被放置到网格点。首先，这样的位置模型需要额外的距离变量，以制定目标函数。G = ，只有2·| V |·| E |变量在模型中的位置，相比变量模型。这种差异呈指数增长的网格尺寸。此外，可行解的数量在我们的模型中，不一致的，例如，嵌入共享一个共同的距离矢量。另一方面，嵌入性的约束数指数和没有多项式的分离方法是迄今已知。位置变量模型可以很容易地扩展到其他度量。然而，关于度量，我们的稀疏图上的计算实验表明，当我们应用基于距离模型分支和切割算法的时候，相同的解决方案的质量可以得到高达103倍的速度时。

4 有效的不等式

在本节中，我们提出了进一步加强上述模型的不等式。

4.1 奇偶校验约束

为了表示一些距离的总和需要奇数或偶数，我们可以利用奇偶约束。

定义8：奇偶校验约束集与G的子图H的相关被定义为这些可嵌入性的约束的集合，在这个约束里d是一个距离矢量的奇。

命题1：如果G是周期的，那么奇偶校验约束集的H是G的k维间隙的所有可行解对于所有的kge;1都满足。

证明：考虑一个着色颜色黑白棋盘的方式，即，任意选择一个起点和颜色白色，然后每个黑颜色（白色，分别。）如果从S到V的距离等于1除以2（0除以2，分别）。考虑一个嵌入在w.l.o.g.美国每边均匀（奇数，分别）长度相同的端节点（不同颜色，分别）和H的开始和终止于白色的，我们的结论是，奇数边的长度数必须甚至。因此，嵌入的周期H的总的边缘长度是均匀的。由于此属性为H的每一个嵌入属性，命题被证明。

4.2 超度不等式

定义9：对于给定的和不等式称为超度不等式。

我们得到了所谓的三角不等式此外。他们显然是K3有效的每一个嵌入。Deza和Laurent [ 11 ]表明，超度不等式任何嵌入的完全图Kn为度量空间都是有效的。因此，对一个图，满足所有所有超度不等式对于任何G中的phi;嵌入是有效。对于一个非完全图的G，这种情况意味着，如果总和在G的一个团的顶点上，那么超度不等式是唯一有效的。

4.3 等级限制

在这一部分，我们考虑G的子图，任何嵌入的总边缘长度可以有简单下边界的，但很容易计算边界。这个K = 1的所谓的秩约束的方法由liu和Vannelli [ 9 ]提出的。因为一个微不足道的下限通常由边缘| Ersquo;|数量，我们将使用不同的作为约束性措施。如果则界是明显的。这是足以寻找极小图Grsquo;（相对于包含）一定质量，因为相应的不等式支配那些超级图Grsquo;rsquo; of Grsquo;提供相同质量Q(Grsquo;rsquo;)= Q(Grsquo;)。

命题2：设表示一个图和一个满足= 的）的子图。然后是的总和以及对于所有。

证明：左边是相同的。从Q(G)= Q(Grsquo;)得到。因此，，显示右侧的双方是平等的。

定义10：如果是满足G在最佳GAP值，我们称的秩约束由G引起。

4.3.1 奇数周期的不等式

偶数循环的秩约束的右边是其边的个数。然而，对于奇数周期，我们得到非平凡的约束。

命题3：如果是一个周期的长度为，那么它在每个维度的秩约束满足。

证明：一个嵌入价值是不可能为一个循环独嵌入偶数的总边缘长度（见命题1）。当最小边长度为1时，较低的值是不可能的。

图 3 各个DxQy图

4.3.2 星形不等式

星形是一个所有的边都有一个共同的所谓的中心节点Endnode的图，我们提出的在Z2最佳嵌入是证明星形的一个显式。

命题4：对于星形图，诱导秩约束是

，。

4.3.3 不等式集合

最小嵌入一个团图是平凡的1维差距因为任何最小线性排列的顶

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[141614]，资料为PDF文档或Word文档，PDF文档可免费转换为Word