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 ProceedingsResearchpeer-review

    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

    Polynomials

    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). Berlin: Springer.
    Fellows, M. ; Langston, M ; Rosamond, F. ; Shaw, P. / Efficient parameterized preprocessing for cluster editing. Lecture Notes in Computer Science. Vol. 4639 LNCS Berlin : Springer, 2007. pp. 312-321
    @inproceedings{f4f7bcc22f24440d90bb1d7afd323c67,
    title = "Efficient parameterized preprocessing for cluster editing",
    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. {\circledC} Springer-Verlag Berlin Heidelberg 2007.",
    keywords = "Edge detection, Graph theory, Polynomials, Edge deletion, Edge insertion, Kernelization bound, Structural reduction rule, Cluster analysis",
    author = "M. Fellows and M Langston and F. Rosamond and P. Shaw",
    year = "2007",
    language = "English",
    isbn = "0302-9743",
    volume = "4639 LNCS",
    pages = "312--321",
    booktitle = "Lecture Notes in Computer Science",
    publisher = "Springer",
    address = "Switzerland",

    }

    Fellows, M, Langston, M, Rosamond, F & Shaw, P 2007, Efficient parameterized preprocessing for cluster editing. in Lecture Notes in Computer Science. vol. 4639 LNCS, Springer, Berlin, pp. 312-321, FCT 2007. International Symposium on Fundamentals of Computation Theory, 27/08/07.

    Efficient parameterized preprocessing for cluster editing. / Fellows, M.; Langston, M; Rosamond, F.; Shaw, P.

    Lecture Notes in Computer Science. Vol. 4639 LNCS Berlin : Springer, 2007. p. 312-321.

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

    TY - GEN

    T1 - Efficient parameterized preprocessing for cluster editing

    AU - Fellows, M.

    AU - Langston, M

    AU - Rosamond, F.

    AU - Shaw, P.

    PY - 2007

    Y1 - 2007

    N2 - 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.

    AB - 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.

    KW - Edge detection

    KW - Graph theory

    KW - Polynomials, Edge deletion

    KW - Edge insertion

    KW - Kernelization bound

    KW - Structural reduction rule, Cluster analysis

    M3 - Conference Paper published in Proceedings

    SN - 0302-9743

    VL - 4639 LNCS

    SP - 312

    EP - 321

    BT - Lecture Notes in Computer Science

    PB - Springer

    CY - Berlin

    ER -

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