无向图中子集反馈顶点集问题的精确算法

• 作者: 周晓清 肖鸣宇
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: NP难问题 精确算法 测量治之 子集反馈顶点集问题
• 年，卷（期）: 2018,（3）
• 所属期刊栏目: 软件技术与理论
• 页码范围: 493-505
• 页数: 13页
• 分类号: TP301
• 字数: 16617字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2018.00493

摘要

子集反馈顶点集问题是一个经典的NP难问题,该问题是指在一个无向图中删除最少的顶点使得图中某些给定的顶点不在任何圈中.子集反馈顶点集问题包含了经典的最小反馈顶点集、多路割等重要特例问题,并且可应用于电路测试、操作系统解死锁等领域.子集反馈顶点集问题也是精确算法中的一个重要问题,该问题存在一个运行时间为O*(2n)的简单暴力搜索算法,其中n为图中顶点数.直到2011年Fomin等人给出一个运行时间为O*(1.8638n)的算法,这个运行时间界才被打破.文中将该运行时间上界进一步改进到O*(1.7743n).文中的算法是一个分支搜索算法,为了改进该问题的运行时间界,文中对问题的结构性质进行了深入的分析,挖掘出若干有效的规约和分支规则,再采用测量治之方法对算法的运行时间进行分析,最终将运行时间上界给予改进.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周晓清	电子科技大学计算机科学与工程学院	15	56	4.0	7.0
5	肖鸣宇	电子科技大学计算机科学与工程学院	4	7	2.0	2.0