Enumerating Minimal Subset Feedback Vertex Sets |
| |
Authors: | Fedor V Fomin Pinar Heggernes Dieter Kratsch Charis Papadopoulos Yngve Villanger |
| |
Affiliation: | 1. Department of Informatics, University of Bergen, Bergen, Norway 2. LITA, Université Paul Verlaine, Metz, France 3. Department of Mathematics, University of Ioannina, Ioannina, Greece
|
| |
Abstract: | The Subset Feedback Vertex Set problem takes as input a pair (G,S), where G=(V,E) is a graph with weights on its vertices, and S?V. The task is to find a set of vertices of total minimum weight to be removed from G, such that in the remaining graph no cycle contains a vertex of S. We show that this problem can be solved in time O(1.8638 n ), where n=|V|. This is a consequence of the main result of this paper, namely that all minimal subset feedback vertex sets of a graph can be enumerated in time O(1.8638 n ). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|