Fixed-Parameter Algorithms for Graph-Modeled Data Clustering
Falk Hüffner, Rolf Niedermeier, Sebastian Wernicke · WORLD SCIENTIFIC eBooks · 2009
Fixed-parameter algorithms can efficiently find optimal solutions to some NP-hard problems, including several problems that arise in graphmodeled data clustering. 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. Our investigations 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 Clique, Cluster Editing, and Clique Cover.