Cluster editing: Kernelization based on edge cuts

Yixin Cao, Jianer Chen

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

5 Citations (Scopus)

Abstract

Kernelization algorithms for the cluster editing problem have been a popular topic in the recent research in parameterized computation. Thus far most kernelization algorithms for this problem are based on the concept of critical cliques. In this paper, we present new observations and new techniques for the study of kernelization algorithms for the cluster editing problem. Our techniques are based on the study of the relationship between cluster editing and graph edge-cuts. As an application, we present an O(n2)-time algorithm that constructs a 2k kernel for the weighted version of the cluster editing problem. Our result meets the best kernel size for the unweighted version for the cluster editing problem, and significantly improves the previous best kernel of quadratic size for the weighted version of the problem.
Original languageEnglish
Title of host publicationParameterized and Exact Computation - 5th International Symposium, IPEC 2010, Proceedings
Pages60-71
Number of pages12
DOIs
Publication statusPublished - 1 Dec 2010
Externally publishedYes
Event5th International Symposium on Parameterized and Exact Computation, IPEC 2010 - Chennai, India
Duration: 13 Dec 201015 Dec 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6478 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Symposium on Parameterized and Exact Computation, IPEC 2010
CountryIndia
CityChennai
Period13/12/1015/12/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this