Efficient parameterized preprocessing for cluster editing

M. Fellows, M Langston, F. Rosamond, P. Shaw

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review


    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. © Springer-Verlag Berlin Heidelberg 2007.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science
    Place of PublicationBerlin
    Number of pages10
    Volume4639 LNCS
    ISBN (Print)0302-9743
    Publication statusPublished - 2007
    EventFCT 2007. International Symposium on Fundamentals of Computation Theory - Budapest, Hungary
    Duration: 27 Aug 200730 Aug 2007


    ConferenceFCT 2007. International Symposium on Fundamentals of Computation Theory


    Dive into the research topics of 'Efficient parameterized preprocessing for cluster editing'. Together they form a unique fingerprint.

    Cite this