Cluster editing: Kernelization based on edge cuts

Yixin Cao; Jianer Chen

doi:10.1007/978-3-642-17493-3_8

Cluster editing: Kernelization based on edge cuts

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-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 language	English
Title of host publication	Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Proceedings
Pages	60-71
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-17493-3_8
Publication status	Published - 1 Dec 2010
Externally published	Yes
Event	5th International Symposium on Parameterized and Exact Computation, IPEC 2010 - Chennai, India Duration: 13 Dec 2010 → 15 Dec 2010

Publication series

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

Conference

Conference	5th International Symposium on Parameterized and Exact Computation, IPEC 2010
Country/Territory	India
City	Chennai
Period	13/12/10 → 15/12/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

More information

10.1007/978-3-642-17493-3_8

Cite this

Cao, Y., & Chen, J. (2010). Cluster editing: Kernelization based on edge cuts. In Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Proceedings (pp. 60-71). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6478 LNCS). https://doi.org/10.1007/978-3-642-17493-3_8

@inproceedings{d3e40b44dfd74a7e9f15961323e4ca58,

title = "Cluster editing: Kernelization based on edge cuts",

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.",

author = "Yixin Cao and Jianer Chen",

year = "2010",

month = dec,

day = "1",

doi = "10.1007/978-3-642-17493-3_8",

language = "English",

isbn = "3642174922",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "60--71",

booktitle = "Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Proceedings",

note = "5th International Symposium on Parameterized and Exact Computation, IPEC 2010 ; Conference date: 13-12-2010 Through 15-12-2010",

}

Cao, Y & Chen, J 2010, Cluster editing: Kernelization based on edge cuts. in Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6478 LNCS, pp. 60-71, 5th International Symposium on Parameterized and Exact Computation, IPEC 2010, Chennai, India, 13/12/10. https://doi.org/10.1007/978-3-642-17493-3_8

Cluster editing: Kernelization based on edge cuts. / Cao, Yixin; Chen, Jianer.
Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Proceedings. 2010. p. 60-71 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6478 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Cluster editing: Kernelization based on edge cuts

AU - Cao, Yixin

AU - Chen, Jianer

PY - 2010/12/1

Y1 - 2010/12/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=78650854699&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17493-3_8

DO - 10.1007/978-3-642-17493-3_8

M3 - Conference article published in proceeding or book

SN - 3642174922

SN - 9783642174926

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

SP - 60

EP - 71

BT - Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Proceedings

T2 - 5th International Symposium on Parameterized and Exact Computation, IPEC 2010

Y2 - 13 December 2010 through 15 December 2010

ER -

Cluster editing: Kernelization based on edge cuts

Abstract

Publication series

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this