Improved Analysis of Highest-Degree Branching for Feedback Vertex Set
Improved Analysis of Highest-Degree Branching for Feedback Vertex Set
复制标题
DOI：
10.1007/s00453-021-00815-w
复制
发表时间：
2019-05
期刊：
影响因子：
1.1
通讯作者：
Yoichi Iwata;Yusuke Kobayashi
中科院分区：
文献类型：
--
作者：
Yoichi Iwata;Yusuke Kobayashi
最近的经验评估的确切算法forFeedback顶点Sethave证明了效率的最高程度的分支算法与度为基础的修剪。在本文中，我们证明了这种经验快速算法运行的时间，其中的解决方案的大小。这改进了之前由Kociumaka和Pilipczuk获得的最佳时间确定性算法（Inf Process Lett 114：556-560，2014. https://doi.org/10.1016/j.ipl.2014.05.001 ).
Recent empirical evaluations of exact algorithms forFeedback Vertex Sethave demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning. In this paper, we prove that this empirically fast algorithm runs intime, wherekis the solution size. This improves the previous best-time deterministic algorithm obtained by Kociumaka and Pilipczuk (Inf Process Lett 114:556–560, 2014. https://doi.org/10.1016/j.ipl.2014.05.001 ).