平面图团覆盖问题的核心化和参数化算法

平面图团覆盖问题的核心化和参数化算法 A New Kernelization and Parameterized Algorithm for the Planar Clique Cover Problem 张文琰 ZHANG Wenyan 1 first-author Rudolf Fleischer Rudolf Fleischer 1 复旦大学计算机科学技术学院/上海智能信息处理重点实验室 复旦大学计算机科学技术学院/上海智能信息处理重点实验室 School of Computer Science/Shanghai Key Laboratory of Intelligent Information Processing, Fudan University School of Computer Science/Shanghai Key Laboratory of Intelligent Information Processing, Fudan University 团覆盖问题是经典的理论计算问题,本文从参数理论角度考虑平面图团覆盖问题,提出了核心化简化规则,通过这些简化规则可以得到平面图团覆盖问题的核心,其规模为4k-4.根据该问题核心设计了参数化算法,可以用O（20k+n2）复杂度求得平面图团覆盖问题的精确解.通过实验与现有的求解团覆盖的算法进行了比较. 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. 平面图团覆盖 核心化 参数化算法 planar clique cover kernelization parameterized algorithm 10.14188/j.1671-8836.2011.06.001 TP301.6 国家自然科学基金（60973026）;上海市重点学科建设基金（B114）;上海科学技术委员会基金（08DZ2271800,09DZ2272800）资助项目 2011-06-01 2021-04-01 6 57