Efficient parameterized preprocessing for cluster editing

M. Fellows; M Langston; F. Rosamond; P. Shaw

Efficient parameterized preprocessing for cluster editing

M. Fellows, M Langston, F. Rosamond, P. Shaw

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-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 language	English
Title of host publication	Lecture Notes in Computer Science
Place of Publication	Berlin
Publisher	Springer
Pages	312-321
Number of pages	10
Volume	4639 LNCS
ISBN (Print)	0302-9743
Publication status	Published - 2007
Event	FCT 2007. International Symposium on Fundamentals of Computation Theory - Budapest, Hungary Duration: 27 Aug 2007 → 30 Aug 2007

Conference

Conference	FCT 2007. International Symposium on Fundamentals of Computation Theory
Period	27/08/07 → 30/08/07

Access to Document

https://www.scopus.com/inward/record.uri?eid=2-s2.0-38149122077&partnerID=40&md5=d3f47c53b31e4531a3671ab65a55be4e

Cite this

@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. {\textcopyright} 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",

note = "FCT 2007. International Symposium on Fundamentals of Computation Theory ; Conference date: 27-08-2007 Through 30-08-2007",

}

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. <https://www.scopus.com/inward/record.uri?eid=2-s2.0-38149122077&partnerID=40&md5=d3f47c53b31e4531a3671ab65a55be4e>

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

T2 - FCT 2007. International Symposium on Fundamentals of Computation Theory

Y2 - 27 August 2007 through 30 August 2007

ER -

Efficient parameterized preprocessing for cluster editing

Abstract

Conference

Access to Document

Fingerprint

Cite this