Fomin, Fedor V. and Grandoni, Fabrizio and Lokshtanov, Daniel and Saurabh, Saket (2012) Sharp Separation and Applications to Exact and Parameterized Algorithms. Algorithmica, 63 (3). pp. 692-706. ISSN 1432-0541
Full text not available from this repository.Abstract
Many divide-and-conquer algorithms employ the fact that the vertex set of a graph of bounded treewidth can be separated in two roughly balanced subsets by removing a small subset of vertices, referred to as a separator. In this paper we prove a trade-off between the size of the separator and the sharpness with which we can fix the size of the two sides of the partition. Our result appears to be a handy and powerful tool for the design of exact and parameterized algorithms for NP-hard problems. We illustrate that by presenting two applications. Our first application is a parameterized algorithm with running time O(16 k + o(k) + n O(1)) for the Maximum Internal Subtree problem in directed graphs. This is a significant improvement over the best previously known parameterized algorithm for the problem by [Cohen et al.’09], running in time O(49.4 k + n O(1)). The second application is a O(2 n + o(n)) time and space algorithm for the Degree Constrained Spanning Tree problem: find a spanning tree of a graph with the maximum number of nodes satisfying given degree constraints. This problem generalizes some well-studied problems, among them Hamiltonian Path, Full Degree Spanning Tree, Bounded Degree Spanning Tree, Maximum Internal Spanning Tree and their edge weighted variants.
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Subjects: | Computer sciences |
| Department/unit: | Dipartimento tecnologie innovative > Istituto Dalle Molle di studi sull'intelligenza artificiale |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 08:30 |
| Last Modified: | 23 May 2016 14:24 |
| URI: | http://repository.supsi.ch/id/eprint/4479 |
Actions (login required)
 |
View Item |