zbMATH — the first resource for mathematics

Efficient parameterized preprocessing for cluster editing. (English) Zbl 1135.68511
Csuhaj-Varjú, Erzsébet (ed.) et al., Fundamentals of computation theory. 16th international symposium, FCT 2007, Budapest, Hungary, August 27–30, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74239-5/pbk). Lecture Notes in Computer Science 4639, 312-321 (2007).
Summary: 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.
For the entire collection see [Zbl 1122.68004].

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI