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

发布时间：2018-08-24 20:21

【摘要】：子集反馈顶点集问题是一个经典的NP难问题,该问题是指在一个无向图中删除最少的顶点使得图中某些给定的顶点不在任何圈中.子集反馈顶点集问题包含了经典的最小反馈顶点集、多路割等重要特例问题,并且可应用于电路测试、操作系统解死锁等领域.子集反馈顶点集问题也是精确算法中的一个重要问题,该问题存在一个运行时间为O~*(2~n)的简单暴力搜索算法,其中n为图中顶点数.直到2011年Fomin等人给出一个运行时间为O~*(1.8638n)的算法,这个运行时间界才被打破.文中将该运行时间上界进一步改进到O~*(1.7743n).文中的算法是一个分支搜索算法,为了改进该问题的运行时间界,文中对问题的结构性质进行了深入的分析,挖掘出若干有效的规约和分支规则,再采用测量治之方法对算法的运行时间进行分析,最终将运行时间上界给予改进.
[Abstract]:The subset feedback vertex set problem is a classical NP problem in which the minimal vertices are deleted in an undirected graph so that some given vertices in the graph are not in any cycle. The subset feedback vertex set problem includes classical special case problems such as minimum feedback vertex set, multipath cut and so on. It can be used in circuit testing and operating system deadlock unlocking and so on. The subset feedback vertex set problem is also an important problem in the exact algorithm. There exists a simple brute force search algorithm with running time of Oo * (2n), where n is the number of vertices in a graph. It was not until 2011 that Fomin et al proposed an algorithm with a running time of 1.8638n, which was broken. In this paper, the upper bound of the running time is further improved to Oo * (1.7743n). The algorithm in this paper is a branch search algorithm. In order to improve the running time bound of the problem, the structural properties of the problem are deeply analyzed, and some effective rules and rules are excavated. Then the running time of the algorithm is analyzed by the method of measurement and treatment, and the upper bound of the running time is improved.
【作者单位】：电子科技大学计算机科学与工程学院成都大学信息科学与工程学院
【基金】：国家自然科学基金(61370071)资助
【分类号】：TP301.6

【相似文献】