| 顶点覆盖问题线性内核算法 |
| |
| 引用本文： | 蔡晟,朱洪. 顶点覆盖问题线性内核算法[J]. 计算机研究与发展, 2008, 45(Z1): 53-56 |
| |
| 作者姓名： | 蔡晟 朱洪 |
| |
| 作者单位： | 1. 复旦大学信息工程学院计算机系,上海,200433
2. 华东师范大学软件学院,上海,200062 |
| |
| 基金项目： | 上海市重点学科建设项目 , 国家自然科学基金 |
| |
| 摘 要： | 参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).
|
| 关 键 词： | 参数复杂性 内核化 线性内核 定点覆盖 |
| 修稿时间： | 2007-07-10 |
Linear Kernelization Algorithm for the Vertex Cover Problem |
| |
| Cai Sheng,Rudolf Fleischer,Zhu Hong. Linear Kernelization Algorithm for the Vertex Cover Problem[J]. Journal of Computer Research and Development, 2008, 45(Z1): 53-56 |
| |
| Authors: | Cai Sheng Rudolf Fleischer Zhu Hong |
| |
| Affiliation: | Cai Sheng1,Rudolf Fleischer1,, Zhu Hong21(Department of Computer Science,Fudan University,Shanghai 200433)2(Software School,East China Normal University,Shanghai 200062) |
| |
| Abstract: | |
| |
| Keywords: | parameterized complexity kernelization linear kernel vertex cover |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
