Open Research Newcastle
Browse

Polynomial-time linear kernelization for cluster editing

Download (151.11 kB)
report
posted on 2025-05-13, 11:49 authored by Michael Fellows, Michael Langston, Frances Rosamond, Peter Shaw
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 24k kernelization bound (and possibly a 6k kernelization bound).

History

Publisher

Unpublished

Commissioning body

University of Newcastle

Language

  • en, English

College/Research Centre

Faculty of Health and Medicine

School

School of Medicine and Public Health

Usage metrics

    Reports

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC