On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms

Authors:	Fedor V Fomin Serge Gaspers Artem V Pyatkin Igor Razgon

Affiliation:	(1) Department of Informatics, University of Bergen, 5020 Bergen, Norway;(2) Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug avenue, 630090 Novosibirsk, Russia;(3) Computer Science Department, University College Cork, Cork, Ireland

Abstract:	We present a time $\mathcal {O}(1.7548^{n})$ algorithm finding a minimum feedback vertex set in an undirected graph on n vertices. We also prove that a graph on n vertices can contain at most 1.8638ⁿ minimal feedback vertex sets and that there exist graphs having 105^n/10≈1.5926ⁿ minimal feedback vertex sets. Preliminary extended abstracts of this paper appeared in the proceedings of SWAT’06 29] and IWPEC’06 18]. Additional support of F.V. Fomin, S. Gaspers and A.V. Pyatkin by the Research Council of Norway. The work of A.V. Pyatkin was partially supported by grants of the Russian Foundation for Basic Research (project code 05-01-00395), INTAS (project code 04–77–7173). I. Razgon is supported by Science Foundation Ireland (Grant Number 05/IN/I886).

Keywords:	Minimum feedback vertex set Maximum induced forest Exact exponential algorithm Number of minimal feedback vertex sets
本文献已被 SpringerLink 等数据库收录！