资源描述：
《二分图的受约束最小点覆盖问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、分类号编号中南大学硕士学位论文论文题目二只分图的受约束最小点覆盖问题研究学科、专业………计算主叹甩技木………二…研究生姓名连一飞二双导师姓名及专业技术职务陈建只…教授年月ConstrainedMinimum、卜卫坦立里亚塑五旦塑丝原创性声明本人声明,所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了论文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均己在在论文中作了
2、明确的说明。作者签名日期兰多即丝一年上月卫店主日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定,即学校有权保留学位论文,允许学位论文被查阅和借阅学校可以公布学位论文的全部或部分内容,可以采用复印、缩印或其它手段保存学位论文学校可根据国家或湖南省有关部门规定送交学位论文。作者签名导师签名阵丸日期补宝回一年上月竺日摘要随着超大规模集成电路技术的发展,关于可重构阵列的二分图受约束最小点覆盖问题简称一问题受到了很多文献的关注,大量这方面的论文发表在的重要期刊和年会上。该问题己被证明是一完全问题。目前求解一
3、问题的精确算法的运行时间为十勺,其中、分别表示备用行和备用列的数目。本文进一步深入分析二分图的结构,对含有权值大于或等于的块的连通子图首先分析其可能连接情况,然后充分利用“链暗示”技术和分枝搜索技术建立新的搜索递推关系对于分枝后的块,本文提出了一种动态规划算法,使其可在多项式时间内完成处理。整个算法的运行时间为勺。在此基础上,本文通过进一步运用参数计算技术和图论知识,研究了一问题的一个亚指数时间算法,该算法尚需进一步完善和补充。同时,针对传统启发式算法和当前精确算法的不足,本文通过进一步深入运用参数计算技术和图论技术,
4、提出了一问题的一个近似算法。该算法具体为当一问题实例存在受约束最小点覆盖,时,对于任意给定的一个常数,一定可在幼·时间内寻找到一个受约束近似点覆盖瓜',衬,它满足毛讯,饭夕十。该算法在理论和实际应用中都具有重要意义。关键词一问题,参数计算,动态规划,近似算法,“链暗示”技术ABSTRACTWiththeteehniealdeveloPmentofVLSI(verylargesealeintegratedeireuit),一一一一,一'对,,知'一一,一,外,仆勺,,一,,一`,一,,,厦城`,丛二凡,`￡'一拼,,dy
5、namicProgramming,劝,目录第一章绪论”二””””“……“““……””二““…””二”……“”二“…””…“…””………研究背景···············一问题定义……,……,……研究现状……,……,一课题研究目标……,二,……,·····················……论文组织……,二,……第二章二分图的受约束最小点覆盖问题精确算法”一”“””““””””二“…””一…引言……,二,……,……相关参数计算技术、定义和引理……,……核心化技术……,…,……,··········一限定搜索树二,……
6、,……,……,·……相关定义和引理……,二,……,二一问题精确算法……,……,……,…减少搜索空间的策略……,……,……,……,……一。算法……,……,,·······,·····················一一问题精确算法性能分析…,……,……本章小结……,……,……,……第三章二分图的受约束最小点覆盖问题亚指数时间算法””””””二”“”““””二引言……,……,…一问题亚指数时间算法相关概念……,……,……一问题亚指数时间算法……,二分枝搜索……,……动态规划技术,··········,···········
7、··……一问题亚指数时间算法性能分析……,……一问题亚指数时间算法存在的问题……,……,二本章小结……第四章二分图的受约束最小点覆盖问题近似算法二””“”““””“”二“二““””弓言……一问题近似算法相关概念……一问题近似算法…,……,……预处理操作…,……从卜算法……,……,·······……4.4Min一问题近似算法性能分析……,……,……本章小结……,……,,……,……,第五章结束语二”””“”“””““””“…“”””““”“”””””““”“““““”““““,研究工作总结……,··一进一步工作……,……参
8、考文献…”……”二”二”……,“。…“”…“”“……”””二““”…”””二”,”……”致谢二“”…“””””“”“”””“”““““””””…”““”二””二””“……”““……””二““…研究成果……““““”“二“”“”“””…“”…”“”“”“”””““““”““””二”““二“”硕士学位论文第一章绪论第一章绪论为了解决大
