基于搜索树的平面图支配集算法

• 作者: 吴筱天 来心可
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 算法 搜索树 支配集 确定参数可解
• 年，卷（期）: 2011,（6）
• 所属期刊栏目: 图形与图像
• 页码范围: 37-40
• 分类号: TP301.6
• 字数: 2489字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2011.06.008

摘要

许多来自工业应用的优化问题都是NP难问题.确定参数可解FPT作为处理这类问题的另外一种思路,在最近的10多年中受到了广泛的关注.支配集问题是图论中最重要的NP完全的组合优化问题之一,即使对于FPT体系而言,一般图中的支配集问题属于W[2]完全的,意味着不可能设计出复杂度为f(k)n°(1)的算法.在本文中,我们考虑在给定的平面图G=(V,E)中参数化支配集问题,给定参数k,看是否存在大小为k的顶点集合支配图中的其他顶点,当把问题限定在平面图上,这个问题属于确定参数可解.本文给出了基于两组归约规则的搜索树算法,通过使用规约技术化简实例,构造搜索树,得到了复杂度为O(8kn)的算法,同时通过相关实验结果显示了归约规则对算法的作用.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	来心可	复旦大学计算机科学技术学院	1	0	0.0	0.0
2	吴筱天	复旦大学计算机科学技术学院	2	0	0.0	0.0