-
题名无向图中子集反馈顶点集问题的精确算法
被引量:3
- 1
-
-
作者
周晓清
肖鸣宇
-
机构
电子科技大学计算机科学与工程学院
成都大学信息科学与工程学院
-
出处
《计算机学报》
EI
CSCD
北大核心
2018年第3期493-505,共13页
-
基金
国家自然科学基金(61370071)资助
-
文摘
子集反馈顶点集问题是一个经典的NP难问题,该问题是指在一个无向图中删除最少的顶点使得图中某些给定的顶点不在任何圈中.子集反馈顶点集问题包含了经典的最小反馈顶点集、多路割等重要特例问题,并且可应用于电路测试、操作系统解死锁等领域.子集反馈顶点集问题也是精确算法中的一个重要问题,该问题存在一个运行时间为O~*(2~n)的简单暴力搜索算法,其中n为图中顶点数.直到2011年Fomin等人给出一个运行时间为O~*(1.8638n)的算法,这个运行时间界才被打破.文中将该运行时间上界进一步改进到O~*(1.7743n).文中的算法是一个分支搜索算法,为了改进该问题的运行时间界,文中对问题的结构性质进行了深入的分析,挖掘出若干有效的规约和分支规则,再采用测量治之方法对算法的运行时间进行分析,最终将运行时间上界给予改进.
-
关键词
NP难问题
精确算法
测量治之
子集反馈顶点集问题
-
Keywords
NP-hard problem
exact algorithms
measure-and-conquer
the subset feedbackvertex set problem
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-