Efficient Parameterized Preprocessing for Cluster Editing
- 27 August 2007
- conference paper
- Published by Springer Nature in Lecture Notes in Computer Science
- Vol. 4639, 312-321
Abstract
In the Cluster Editing problem, a graph is to be changed to a disjoint union of cliques by at most k operations of edge insertion or edge deletion. Improving on the best previously known quadratic-size polynomial-time kernelization, we describe how a crown-type structural reduction rule can be used to obtain a 6k kernelization bound.Keywords
This publication has 19 references indexed in Scilit:
- Parameterized enumeration, transversals, and imperfect phylogeny reconstructionTheoretical Computer Science, 2006
- Fixed-Parameter Tractable Generalizations of Cluster EditingLecture Notes in Computer Science, 2006
- Clustering with qualitative informationJournal of Computer and System Sciences, 2005
- Computational, Integrative, and Comparative Methods for the Elucidation of Genetic Coexpression NetworksBioMed Research International, 2005
- On the Fixed-Parameter Enumerability of Cluster EditingLecture Notes in Computer Science, 2005
- Correlation ClusteringMachine Learning, 2004
- Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized ComplexityLecture Notes in Computer Science, 2004
- Computing Phylogenetic Roots with Bounded Degrees and ErrorsSIAM Journal on Computing, 2003
- Parameterized Complexity1999
- Fixed-parameter tractability of graph modification problems for hereditary propertiesInformation Processing Letters, 1996