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 Proceedings

    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. © Springer-Verlag Berlin Heidelberg 2007.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science
    Place of PublicationBerlin
    PublisherSpringer
    Pages312-321
    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

    Conference

    ConferenceFCT 2007. International Symposium on Fundamentals of Computation Theory
    Period27/08/0730/08/07

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

  • Cite this

    Fellows, M., Langston, M., Rosamond, F., & Shaw, P. (2007). Efficient parameterized preprocessing for cluster editing. In Lecture Notes in Computer Science (Vol. 4639 LNCS, pp. 312-321). Springer.