最小赋权连通k-子图覆盖问题的近似算法

发布时间：2017-10-14 15:26

  本文关键词：最小赋权连通k-子图覆盖问题的近似算法

  更多相关文章： 点覆盖 k-长路覆盖 连通k-子图覆盖 三正则图

【摘要】：一个顶点子集F被称作是一个连通k-子图覆盖(记作V CCk)如果任意k个点的连通子图至少有一个顶点在集合F中.最小赋权的连通k-子图覆盖问题(记作MWV CCk)是指找一个权和最小的顶点子集F使得图G的顶点集去掉F后剩下的图不含k个点的连通子图.这个问题在安全方面和监控方面有它的实际背景,它是最小赋权点覆盖问题的推广,而且与最小赋权k-长路覆盖问题(记作MWV CPk)有关,这个问题要求每个k-长路中的点至少有一个顶点在子集F中.通过线性规划的舍入技巧很容易得到一个k-近似算法.在本文中,首先,我们提出了一个与MWV CPk相关的模型,即抽象化为一般图中连通k-子图覆盖问题,它是对MWV CPk问题的一种松弛,并且在假定给出图的围长(最短圈的长度)至少为k的条件下,我们给出了该问题在赋权情况下的k-1-近似算法,而且构造出了一些例子,来说明对于我们这个算法其k-1是紧的,对于k=3,在[30]中,涂建华等人对于MWV CP3问题给出了一个2-近似算法,由于MWV CP3和MWV CC3是同一个问题,而且一个简单图的围长至少为3,因此,涂等人的结果[30]被包含在我们的结果中.其次,在正则图中,我们也得到了一些比较好的结果,对于k=3,4,5,分别得到了54,2,3.5-近似算法,并对于k=3,4的情形,构造出了相应的紧例子,对于一般的k,k≥6,若k是偶数,得到k2-近似,若k是奇数,得到3k4-近似.最后,我们做了简单的总结,并且讨论了今后我们所感兴趣的领域.
【关键词】：点覆盖 k-长路覆盖 连通k-子图覆盖 三正则图
【学位授予单位】：新疆大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要2-3
• 英文摘要3-5
• 第一章 引言5-8
• 1.1 研究背景5-6
• 1.2 研究现状6-7
• 1.3 本论文的主要结果7-8
• 第二章 一般图中连通k-子图覆盖问题的近似算法8-14
• 2.1 预备知识8-10
• 2.2 算法10-11
• 2.3 近似比及复杂度分析11-14
• 第三章 三正则图中连通k-子图覆盖问题的近似算法14-20
• 3.1 预备知识14-16
• 3.2 近似算法16-17
• 3.3 近似比分析17-20
• 第四章 讨论及总结20-21
• 参考文献21-24
• 硕士期间发表及完成论文清单24-25
• 致谢25-26

【共引文献】

中国硕士学位论文全文数据库 前2条

1 崔振华;覆盖约束条件下的平行机排序问题的算法研究[D];清华大学;2013年

2 李玉超;顶点覆盖k-路问题的研究和富勒烯图的参数计算[D];北京化工大学;2014年

，

本文编号：1031812