【摘 要】
：
组合优化领域最经典的NP-困难问题之一,点覆盖问题,它指的是用最少的点来覆盖图中的所有的边.后来,在2010年Bresar等人对此问题进行了推广,提出了 k-路点覆盖问题(MVCPk),即
论文部分内容阅读
组合优化领域最经典的NP-困难问题之一,点覆盖问题,它指的是用最少的点来覆盖图中的所有的边.后来,在2010年Bresar等人对此问题进行了推广,提出了 k-路点覆盖问题(MVCPk),即寻找图G的一个最小顶点集F使得任意一条k-路至少有一个点被包含在F中.如果一个VCPk,其导出子图连通,则称为最小连通k-路点覆盖问题,记为MCVCPk.当考虑加权的情况,目标就是找到一个权和最小的VCPk(简称MWVCPk).Liu等人给出了在单位圆盘图上对于连通的MCVCPk问题的PTAS近似算法.以及Zhang等人给出了在球图上对于最小点覆盖问题的PTAS近似算法.那么对于球图上的MVCPk问题而言,是否也能得到PTAS的近似算法呢?本文主要使用局部搜索方法,对于球图上MVCPk问题,在球图中的所有球中的最大半径与最小半径的比值有一个常数上界时,给出一个PTAS近似算法.同时给出MCVCPk在单位圆盘图上的一个简化算法.它不再象Liu等的文章中那样需要基于一个常数近似算法,算法和分析过程也比Liu等的文章有极大的简化.本学位论文共分五章:在第一章中,我们介绍一些准备知识,以及相关领域的研究现状.第二章中,我们研究了在球图上的MVCPk问题,并且给出其近似比以及复杂性分析.第三章中,基于对MVCPk问题的进一步推广,进一步研究了在球图上m-重的MVCPk问题.第四章中,我们给出单位圆盘图上的CVCPk问题的一个简化的PTAS近似算法.第五章中,基于以上问题的讨论与总结.
其他文献
信息隐藏技术是信息安全领域中的一个热门研究方向,可广泛地用于机密信息的安全存储与传输、隐蔽通信、数字媒体的版权保护等。但信息隐藏技术也可能被恶意滥用,如秘密窃取机
场景分类一直是计算机视觉领域的一个难点,在数字图像管理、视频监控、遥感图像处理等领域有着诸多应用。随着社会成像探测技术的迅猛发展以及高速通信网络的构建,产生了海量
随着世界气候变化和经济的急速的发展,生态环境遭受到严重破坏,并在日常生活中的各种水问题已经变得越来越严重。为了进一步探讨水资源与环境的问题,为合理利用水资源提供理论依据,博斯腾湖流域的人们最终面临的是水,水和自然发展。在博斯腾湖整体的流域内正确使用的湖泊,河流和地下水,应用环境同位素技术,在对博斯腾湖流域的开都河、清水河、黄水沟及周边地下水采样进行氢氧稳定同位素测定的基础上,分析“三水”之间的供应
在中国经济高速发展和人民日益提高的物资生活水平下,人们消费水平的提高和对产品的高追求迫使企业不得不对产业进行升级,早期传统行业过多的投入和转型的困境使生产与当前的
目前我国正处于新常态下的“转型期”,各行业面临着新的机遇和挑战。私募证券基金,是我国资本市场上的一股新生力量。笔者在工作中发现,很多私募基金存在着战略管理问题,本文
在最近的近十年里,很多发展中国家致力于促进智能电网的建设与发展。应用智能电网相比传统电网,可以通过用户用电行为辨识算法来判断用户的用电模式并进行分类,对实现需求响应和电价制定具有重要意义。针对K均值算法中用电数据特征选取策略问题,本文提出了一种考虑特征间相关关系的迭代型特征优选策略。首先基于DBI指标对不同特征组合下的K均值聚类效果来作为特征选取的标准;然后,建立特征优选模型,通过实验将备选特征优
随着互联网相关技术的快速发展,在以微博、淘宝等为代表的新型自媒体上,用户自由地在网络平台上表述自己的观点。评论观点不仅是用户选购产品或讨论时事的参考依据,也是收集
最近几年,随着物联网(Internet of Things,IoT)快速的进入到各个行业中,传感器网络(Wireless Sensor Networks,WSNs)作为IoT发展的一个重要推动者,基本都是依靠电池充电的,但
随着社会经济飞速发展,我国各项基础设施建设一路高歌猛进,产值规模不断扩张,但是建筑施工安全管理方面自动化程度仍然较低,施工现场脚手架和施工人员状态实时监测、风险状态评价和信息综合管理困难。因此,研发集现场检测设备和智能风险监测软件于一体的施工现场智能网联监测系统具有重要现实意义。论文在对建筑工程施工安全管理的研究基础上,通过施工现场风险源辨识,构建脚手架及施工人员风险评价指标体系,并设计出一套基于
社会治理是实现社会稳定运行的方式方法和动态过程。社会治理伴随着人类社会的产生而出现,随着社会的发展而发展。无论是古代社会、亚细亚社会还是殖民社会,亦或是市民社会,