On parameterized enumeration

DSpace Repository


URI: http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-11980
Dokumentart: Report
Date: 2001
Source: WSI ; 2001 ; 21
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Sonstige - Informations- und Kognitionswissenschaften
DDC Classifikation: 004 - Data processing and computer science
Keywords: Tübingen / Wilhelm-Schickard-Institut für Informatik
License: http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=de http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=en
Show full item record


We study several versions of parameterized enumeration. The idea is always to have an algorithm which outputs all solutions (in a certain sense) to a given problem instance. Such an algorithm will we analysed from the viewpoint of parameterized complexity. We show how to apply enumeration techniques in a number of examples. In particular, we give a fixed parameter algorithm for the reconfiguration of faulty chips when providing so-called shared and linked squares.

This item appears in the following Collection(s)