【作者】 刘清海；

【导师】 张昭；

【作者基本信息】 新疆大学 ， 应用数学， 2012， 博士

【摘要】 组合最优化是指在给定的有限集中,找出按某种目标达到最优的解的一类问题,常见的组合优化问题很多都是NP-困难的.本论文主要研究三类NPˉ困难的优化问题的算法.第二章研究3ˉ连通图3ˉ正则图的最长圈问题,通过组合方法构造出一个长度至少为|G|r的一个圈,其中r≈0.8为方程8.956r+1.036r=10.992r的实数根.这也改进了Jackson等人[40]中的r≈0.753的结论.第三章和第四章研究控制集问题,设G为图, D为G的一个点子集,如果G D中任意一个点都和D中某个点相邻且G[D]连通,则称D为G的一个连通控制集.αMOC-CDS指G的一个连通控制集D满足对任意G的两个点u, v, G中最短的连接u,v的且内部点都在D中的路的长度不超过G中最短(u,v)-路的长度的α倍. Du等人[21]给出了单位圆盘图上α≥5时的一个常数比近似算法.本文第三章考虑α <5的情况,首先给出单位圆盘图上的一个常数比近似算法,然后利用这个算法得到一个多项式时间近似模式算法.设D为G的一个连通控制集,如果对G D中每个点u, D中至少存在k个点到u的距离不超过r,则称D为G的一个r-跳k-连通控制集,简记为(k,r)-连通控制集,第四章首先给出单位圆盘图上(k,r)ˉ控制集的一个两阶段算法,其近似比只与k,r有关,然后对一般图给出一个贪婪算法,其近似比为2rH(r+k r),其中H(·)为调和函数, r为幂图Gr的最大度.更多还原

【Abstract】 In a Combinatorial Optimization Problem, one is required to find an element in afinite set such that the objective function on this element is minimum or maximum. Manycombinatorial optimization problems are NP-hard. Three problems are considered in thisthesis. In Chapter2, we find a circle in a3-connected3-regular graph G of length at least|G|rby construction, where r≈0.8is the real root of8.956r+1.036r=10.992r. Thisresult improves the previous work of Jackson [40] in which r≈0.753.In Chapter3and Chapter4, dominating set problems are considered. Let G be agraph, a vertex subset D of G is said to be a connected dominating set of G, if everyvertex of G D has at least one neighbor in D and G[D], the subgraph induced by D,is connected. A connected dominating set D is called an αMOC-CDS if for any vertexu, v of G, there is an (u, v)-path of G whose internal vertices lie in D and whose lengthis at most α times the length of the shortest (u, v)-path in G. In [21], Du et. al. gavea constant factor approximation algorithm on unit disk graph for the case α≥5. InChapter3, we consider the case α <5and give two approximation algorithms on unitdisk graphs. The first one is a constant factor approximation algorithm. The second oneis a polynomial time approximation scheme based on the first one.Let D be a connected dominating set of G. If for any vertex u of G D, there are atleast k vertices in D which are at most r hops away from u, then D is called a connectedr-hop k-dominating set, or (k, r)-CDS for short. In Chapter4, Two approximation al-gorithms for (k, r)-CDS problem are presented. The first one is a two-step algorithm onunit disk graphs whose approximation ratio only depends on k and r. The second oneis a greedy algorithm on general graphs whose approximation ratio is2rH(r+k r),where H(·) is harmonic function, ris the maximum degree in the power graph Gr.更多还原