【摘要】：子集反饋頂點集問題是一個經(jīng)典的NP難問題,該問題是指在一個無向圖中刪除最少的頂點使得圖中某些給定的頂點不在任何圈中.子集反饋頂點集問題包含了經(jīng)典的最小反饋頂點集、多路割等重要特例問題,并且可應(yīng)用于電路測試、操作系統(tǒng)解死鎖等領(lǐng)域.子集反饋頂點集問題也是精確算法中的一個重要問題,該問題存在一個運行時間為O~*(2~n)的簡單暴力搜索算法,其中n為圖中頂點數(shù).直到2011年Fomin等人給出一個運行時間為O~*(1.8638n)的算法,這個運行時間界才被打破.文中將該運行時間上界進一步改進到O~*(1.7743n).文中的算法是一個分支搜索算法,為了改進該問題的運行時間界,文中對問題的結(jié)構(gòu)性質(zhì)進行了深入的分析,挖掘出若干有效的規(guī)約和分支規(guī)則,再采用測量治之方法對算法的運行時間進行分析,最終將運行時間上界給予改進.
[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

【相似文獻】

相關(guān)期刊論文 前10條

1 祝傳忠;圖中有H圈的充分條件[J];華中理工大學學報;1989年01期

2 王永茂，孟憲云，張惠娟;圖的棱凝聚度的若干性質(zhì)[J];淮海工學院學報(自然科學版);1994年01期

3 邵澤輝;許曉東;羅海鵬;;兩個多色頂點Folkman數(shù)的界[J];計算機應(yīng)用研究;2009年03期

4 龔如華,樂曉波;數(shù)據(jù)相關(guān)性分析的非精確算法[J];中南工業(yè)大學學報;1997年04期

5 白生明,張洪波;在地圖上量算面積的精確算法[J];油氣田地面工程;2000年01期

6 朱志軍;熊偉;王超;陳宏盛;;地理柵格影像的時空聚集精確算法[J];計算機工程與科學;2012年03期

7 李紹華;王建新;馬振宇;陳建二;;基于加權(quán)分治技術(shù)的set packing精確算法[J];小型微型計算機系統(tǒng);2010年06期

8 鄭興華;濾除衰減直流分量的全周傅氏精確算法[J];浙江電力;1998年01期

9 尹丹;高宏;鄒兆年;;一種新的高效圖聚集算法[J];計算機研究與發(fā)展;2011年10期

10 支志兵;寧愛兵;熊小華;王永斐;陳吉珍;楊曉芳;;刪除頂點生成二分圖問題的精確算法[J];小型微型計算機系統(tǒng);2014年09期

相關(guān)博士學位論文 前2條

1 孫永奇;若干圖的Ramsey數(shù)研究[D];大連理工大學;2006年

2 包曉光;一些路線問題的算法設(shè)計與分析[D];華東理工大學;2012年

相關(guān)碩士學位論文 前2條

1 周陽;最大團問題的精確算法研究[D];華中科技大學;2015年

2 石磊;使用度量與分治方法分析和設(shè)計精確算法[D];上海交通大學;2010年

，

本文編號：2201933