| 平面图团覆盖问题的核心化和参数化算法 |
| |
| 引用本文： | 张文琰.平面图团覆盖问题的核心化和参数化算法[J].武汉大学学报(理学版),2011,57(6):461-464. |
| |
| 作者姓名： | 张文琰 |
| |
| 作者单位： | 复旦大学计算机科学技术学院／上海智能信息处理重点实验室,上海,200433 |
| |
| 基金项目： | 国家自然科学基金(60973026); 上海市重点学科建设基金(B114); 上海科学技术委员会基金(08DZ2271800,09DZ2272800)资助项目 |
| |
| 摘 要： | 团覆盖问题是经典的理论计算问题,本文从参数理论角度考虑平面图团覆盖问题,提出了核心化简化规则,通过这些简化规则可以得到平面图团覆盖问题的核心,其规模为4k-4.根据该问题核心设计了参数化算法,可以用O（20k＋n2）复杂度求得平面图团覆盖问题的精确解.通过实验与现有的求解团覆盖的算法进行了比较.
|
| 关 键 词： | 平面图团覆盖 核心化 参数化算法 |
A New Kernelization and Parameterized Algorithm for the Planar Clique Cover Problem |
| |
| ZHANG Wenyan,Rudolf Fleischer.A New Kernelization and Parameterized Algorithm for the Planar Clique Cover Problem[J].JOurnal of Wuhan University:Natural Science Edition,2011,57(6):461-464. |
| |
| Authors: | ZHANG Wenyan Rudolf Fleischer |
| |
| Institution: | ZHANG Wenyan,Rudolf Fleischer(School of Computer Science/Shanghai Key Laboratory of Intelligent Information Processing,Fudan University,Shanghai 200433,China) |
| |
| Abstract: | The Clique Cover Problem is a classical theoretical computing problem.In this paper,we study the parameterized complexity of the Planar Clique Cover Problem.We design several reduction rules to get a kernel of size 4k-4.This leads to a parameterized algorithm that can get the exact solution of the problem in O(20k+n2) time.We implemented the algorithm and compared its performance with previous algorithms. |
| |
| Keywords: | planar clique cover kernelization parameterized algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
