平面图上固定参数可解问题的核心化

摘要：

区域划分技术是目前唯一的在平面图上设计固定参数可解(FPT)问题的一般性方法. 利用该方法可以设计一系列满足一定条件的FPT 问提在平面图上的核，该方法的缺点是往往很难精确分析实际核的大小.提出另一种更简单，直观，在平面上设计及分析FPT 问题核的方法. 利用该方法,改进了连通点覆盖(connected vertex cover), 树覆盖(tree cover), 巡游覆盖(tour cover), 边支配集(edgedominating set) 以及点不相交三角形Packing(vertex disjoint K3 packing)问题在平面图上的核，且所有得到的核均是紧的. 同时同时将结果推广到了亏格及围长限定的图上。

关键词： Keyword: connected vertex cover tree cover tour cover edge dominating set vertex disjoint K3 packing kernelization genus girth

作者: 杨勇杰 王伟平

作者单位: 中南大学信息科学与工程学院 长沙 410083

会议类型: 国内会议

会议名称: 湖南省第三届研究生创新论坛——信息与控制工程的新理论和新技术分论坛

会议地点: 长沙

会议语种:中文

页码: 68-79

在线出版日期: 2010-11-01（万方平台首次上网日期，不代表论文的发表时间）