論文

査読有り
2015年8月

An improved exact algorithm for undirected feedback vertex set

JOURNAL OF COMBINATORIAL OPTIMIZATION
  • Mingyu Xiao
  • ,
  • Hiroshi Nagamochi

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

エクスポート
BibTeX RIS