Biology Reference
In-Depth Information
Chapter 1
Fixed-Parameter Algorithms for
Graph-Modeled Data Clustering
Falk H uffner
∗
Institut f ur Informatik, Friedrich-Schiller-Universitat Jena
Ernst-Abbe-Platz 2, D-07743 Jena, Germany
hueffner@minet.uni-jena.de
Rolf Niedermeier
Institut f ur Informatik, Friedrich-Schiller-Universitat Jena
Ernst-Abbe-Platz 2, D-07743 Jena, Germany
niedermr@minet.uni-jena.de
Web: http://theinf1.informatik.uni-jena.de/
Sebastian Wernicke
†
Institut f ur Informatik, Friedrich-Schiller-Universitat Jena
Ernst-Abbe-Platz 2, D-07743 Jena, Germany
wernicke@minet.uni-jena.de
Fixed-parameter algorithms can efficiently find optimal solutions to some NP-
hard problems, including several problems that arise in graph-modeled data clus-
tering. This survey provides a primer about practical techniques to develop such
algorithms; in particular, we discuss the design of
kernelizations
(data reductions
with provable performance guarantees) and
depth-bounded search trees
.Ourin-
vestigations are circumstantiated by three concrete problems from the realm of
graph-modeled data clustering for which fixed-parameter algorithms have been
implemented and experimentally evaluated, namely C
LIQUE
,C
LUSTER
E
DIT
-
ING
,andC
LIQUE
C
OVER
.
Search WWH ::
Custom Search