An improved exact algorithm for undirected feedback vertex set
An improved exact algorithm for undirected feedback vertex set
复制标题
DOI：
10.1007/s10878-014-9737-x
复制
发表时间：
2013-12
影响因子：
1
通讯作者：
Mingyu Xiao;H. Nagamochi
中科院分区：
文献类型：
--
作者：
Mingyu Xiao;H. Nagamochi
无向图中的反馈顶点集是一个顶点的子集，如果去掉它，图就没有圈了。Razgon(见：第十届斯堪的纳维亚算法理论研讨会论文集(SWAT 2006)，第160-171页，2006)给出了在一个顶点无向图中寻找最小反馈顶点集的一个时间算法，这是第一个打破平凡障碍问题的精确算法。后来，Fomnet等人(算法mica 52：293-307,2008)将结果改进为。在本文中，我们将结果进一步改进为。通过测量和征服的方法对算法进行了分析。基于实例的双连通性设计了新的约简，并在约简图的结构上引入了新的度量方案，从而得到了改进。
A feedback vertex set in an undirected graph is a subset of vertices removal of which leaves a graph with no cycles. Razgon (in: Proceedings of the 10th Scandinavian workshop on algorithm theory (SWAT 2006), pp. 160–171, 2006) gave a-time algorithm for finding a minimum feedback vertex set in an-vertex undirected graph, which is the first exact algorithm for the problem that breaks the trivial barrier of. Later, Fominet al.(Algorithmica 52:293–307, 2008) improved the result to. In this paper, we further improve the result to. Our algorithm is analyzed by the measure-and-conquer method. We get the improvement by designing new reductions based on biconnectivity of instances and introducing a new measure scheme on the structure of reduced graphs.