最小权和的连通顶点P3覆盖问题

作     者：王利民 

作者单位：南京师范大学 

学位级别：硕士

导师姓名：张晓岩

授予年度：2015年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：多项式时间近似格式 单位圆盘图 单位球图 顶点P3覆盖 c-局部问题 光滑权值 

摘      要：图的顶点覆盖问题是图论研究中的一个热点问题.给定一个简单图G=(E E),选取一个顶点子集S(?)V,如果图中的每一条边至少有一个顶点在集合S中,则称S是图G的一个顶点覆盖集.当图中的每一个顶点v∈V,赋予非负权值w(v),此时就是寻找一个顶点权和最小的顶点覆盖.这个问题是顶点删除问题的一个特殊类.顶点删除问题就是寻找一个最小权和的顶点子集使得从图上删除这些顶点后,剩下的顶点导出的子图满足一个给定的特征.例如：顶点反馈集问题就是寻找一个最小权和的顶点子集S(?)V(G)使得V-S导出的子图G[V一S]不包含圈.受到上述顶点删除问题的启发,作为推广介绍最小权和的连通顶点Pk覆盖问题：寻找一个最小权和的顶点子集S(?)V(G)使得V-S导出的子图G[V-S]不包含Pk路,且S导出的子图G[S]是连通的,其中Pk是指有k个顶点的路.在本论文中主要考虑k=3的情况.对于顶点P3覆盖问题,已经有许多比较好的结果Bostjan (2011)证明最小顶点Pk(k是整数,k≥2)覆盖问题在一般图上是NP-完全的,Tu和Zhou(2011)利用原始对偶近似算法给出最小权和的顶点P3覆盖问题的一个2因子近似解.考虑到连通性,Liu(2013)等人给出了最小的连通顶点Pk覆盖问题在单位圆盘图上的一个近似解.但对于顶点加权和连通性的情况还没有结果,为此本文在这两个条件下考虑顶点P3覆盖问题在一些特殊图上的近似算法.本文共有四章内容,主要是研究几类特殊图的最小权和的连通顶点P3覆盖问题的多项式时间近似格式.第一章给出了文章用到的相关符号,基本概念以及顶点Pk覆盖问题的应用背景和已有的结论,并进一步阐述本文的方法和主要结果.在第二章中,首先证明这个问题在网格图上的NP-复杂性,其次得出这个问题在单位圆盘图上的一个常因子近似解,最后在假设最小权和的连通顶点P3覆盖问题是c-局部的和图的最小度是2的条件下,本文证明在单位圆盘图上可以求得这个问题的一个多项式时间近似格式.在第三章中,在最小权和的连通顶点P3覆盖问题是弱c-局部的和图的顶点权值是光滑性的条件下,本文证明在单位球图上可以求得这个问题的一个多项式时间近似格式.文章的最后,给出一些可以进一步探讨的问题.