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

摘要

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