Iterative Compression and Exact Algorithms

Author	dc.contributor.author	Fomin, Fedor V.
Author	dc.contributor.author	Gaspers, Serge	es_CL
Author	dc.contributor.author	Kratsch, Dieter	es_CL
Author	dc.contributor.author	Liedloff, Mathieu	es_CL
Author	dc.contributor.author	Saurabh, Saket	es_CL
Admission date	dc.date.accessioned	2010-06-17T19:21:40Z
Available date	dc.date.available	2010-06-17T19:21:40Z
Publication date	dc.date.issued	2010
Identifier	dc.identifier.uri	https://repositorio.uchile.cl/handle/2250/125353
Abstract	dc.description.abstract	Iterative Compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our ndings with algorithms for the Maximum Independent Set problem, a parameterized and a counting version of d-Hitting Set and the Maximum Induced Cluster Subgraph problem.	en_US
Lenguage	dc.language.iso	en	en_US
Título	dc.title	Iterative Compression and Exact Algorithms	en_US
Document type	dc.type	Artículo de revista