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

作     者：张文琰 Rudolf Fleischer 

作者机构：复旦大学计算机科学技术学院/上海智能信息处理重点实验室上海200433 

基　　金：国家自然科学基金(60973026) 上海市重点学科建设基金(B114) 上海科学技术委员会基金(08DZ2271800,09DZ2272800)资助项目 

出 版 物：《武汉大学学报（理学版）》 (Journal of Wuhan University:Natural Science Edition)

年 卷 期：2011年第57卷第6期

页      码：461-464页

摘      要：团覆盖问题是经典的理论计算问题,本文从参数理论角度考虑平面图团覆盖问题,提出了核心化简化规则,通过这些简化规则可以得到平面图团覆盖问题的核心,其规模为4k-4.根据该问题核心设计了参数化算法,可以用O(20k+n2)复杂度求得平面图团覆盖问题的精确解.通过实验与现有的求解团覆盖的算法进行了比较.

主 题 词：平面图团覆盖 核心化 参数化算法 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.14188/j.1671-8836.2011.06.001

馆 藏 号：203580348...