A 2k Kernel for the Cluster Editing Problem Conference Paper

abstract

• The cluster editing problem for a given graph G and a given parameter k asks if one can apply at most k edge insertion/deletion operations on G so that the resulting graph is a union of disjoint cliques. The problem has attracted much attention because of its applications in bioinformatics. In this paper, we present a polynomial time kernelization algorithm for the problem that produces a kernel of size bounded by 2k, improving the previously best kernel of size 4k for the problem. 2010 Springer-Verlag Berlin Heidelberg.

authors

• Chen, Jianer

published proceedings

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

• Chen, J., & Meng, J.

citation count

• 14

complete list of authors

• Chen, Jianer||Meng, Jie

publication date

• August 2010

publisher

• Springer Nature  Publisher

published in

• Lecture Notes in Computer Science  Journal

keywords

• 46 Information And Computing Sciences

Digital Object Identifier (DOI)

• 10.1007/978-3-642-14031-0_49

International Standard Book Number (ISBN) 10

• 3642140300

International Standard Book Number (ISBN) 13

• 9783642140303

start page

• 459

end page

• 468

volume

• 6196

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2F978-3-642-14031-0_49