2015年8月
An improved exact algorithm for undirected feedback vertex set
JOURNAL OF COMBINATORIAL OPTIMIZATION
- ,
- 巻
- 30
- 号
- 2
- 開始ページ
- 214
- 終了ページ
- 241
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/s10878-014-9737-x
- 出版者・発行元
- SPRINGER
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, Fomin et 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.
- リンク情報
-
- DOI
- https://doi.org/10.1007/s10878-014-9737-x
- DBLP
- https://dblp.uni-trier.de/rec/journals/jco/XiaoN15
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000357045600002&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/jco/jco30.html#journals/jco/XiaoN15
- ID情報
-
- DOI : 10.1007/s10878-014-9737-x
- ISSN : 1382-6905
- eISSN : 1573-2886
- DBLP ID : journals/jco/XiaoN15
- Web of Science ID : WOS:000357045600002