The cluster editing problem: Implementations and experiments

F Dehne; M.A. Langston; X. Luo; S. Pitre; P. Shaw; Y Zhang

doi:10.1007/11847250_2

The cluster editing problem: Implementations and experiments

F Dehne, M.A. Langston, X. Luo, S. Pitre, P. Shaw, Y Zhang

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

Abstract

In this paper, we study the cluster editing problem which is fixed parameter tractable. We present the first practical implementation of a FPT based method for cluster editing, using the approach in [6,7], and compare our implementation with the straightforward greedy method and a solution based on linear programming [3]. Our experiments show that the best results are obtained by using the refined branching method in [7] together with interleaving (re-kernelization). We also observe an interesting lack of monotonicity in the running times for "yes" instances with increasing values of k.

Original language	Undefined
Title of host publication	IWPEC
Subtitle of host publication	International Workshop on Parameterized and Exact Computation
Editors	Hans L. Bodlaender, Michael A. Langston
Publisher	Springer
Pages	13-24
Number of pages	12
ISBN (Electronic)	978-3-540-39101-2
ISBN (Print)	978-3-540-39098-5
DOIs	https://doi.org/10.1007/11847250_2
Publication status	Published - 2006
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	4169
ISSN (Print)	0302-9743

Access to Document

10.1007/11847250_2

Link to Scopus publication

Cite this

@inproceedings{0d68bac219e446da80b8cef6686b5bbc,

title = "The cluster editing problem: Implementations and experiments",

abstract = "In this paper, we study the cluster editing problem which is fixed parameter tractable. We present the first practical implementation of a FPT based method for cluster editing, using the approach in [6,7], and compare our implementation with the straightforward greedy method and a solution based on linear programming [3]. Our experiments show that the best results are obtained by using the refined branching method in [7] together with interleaving (re-kernelization). We also observe an interesting lack of monotonicity in the running times for {"}yes{"} instances with increasing values of k. ",

keywords = "Linear programming, Problem solving, Cluster editing, Monotonicity, Artificial intelligence",

author = "F Dehne and M.A. Langston and X. Luo and S. Pitre and P. Shaw and Y Zhang",

year = "2006",

doi = "10.1007/11847250_2",

language = "Undefined",

isbn = "978-3-540-39098-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "13--24",

editor = "Bodlaender, {Hans L.} and Langston, {Michael A.}",

booktitle = "IWPEC",

address = "Switzerland",

}

The cluster editing problem : Implementations and experiments. / Dehne, F; Langston, M.A.; Luo, X.; Pitre, S.; Shaw, P.; Zhang, Y.

IWPEC: International Workshop on Parameterized and Exact Computation. ed. / Hans L. Bodlaender; Michael A. Langston. Springer, 2006. p. 13-24 (Lecture Notes in Computer Science; Vol. 4169).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

TY - GEN

T1 - The cluster editing problem

T2 - Implementations and experiments

AU - Dehne, F

AU - Langston, M.A.

AU - Luo, X.

AU - Pitre, S.

AU - Shaw, P.

AU - Zhang, Y

PY - 2006

Y1 - 2006

N2 - In this paper, we study the cluster editing problem which is fixed parameter tractable. We present the first practical implementation of a FPT based method for cluster editing, using the approach in [6,7], and compare our implementation with the straightforward greedy method and a solution based on linear programming [3]. Our experiments show that the best results are obtained by using the refined branching method in [7] together with interleaving (re-kernelization). We also observe an interesting lack of monotonicity in the running times for "yes" instances with increasing values of k.

AB - In this paper, we study the cluster editing problem which is fixed parameter tractable. We present the first practical implementation of a FPT based method for cluster editing, using the approach in [6,7], and compare our implementation with the straightforward greedy method and a solution based on linear programming [3]. Our experiments show that the best results are obtained by using the refined branching method in [7] together with interleaving (re-kernelization). We also observe an interesting lack of monotonicity in the running times for "yes" instances with increasing values of k.

KW - Linear programming

KW - Problem solving, Cluster editing

KW - Monotonicity, Artificial intelligence

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

U2 - 10.1007/11847250_2

DO - 10.1007/11847250_2

M3 - Conference Paper published in Proceedings

SN - 978-3-540-39098-5

T3 - Lecture Notes in Computer Science

SP - 13

EP - 24

BT - IWPEC

A2 - Bodlaender, Hans L.

A2 - Langston, Michael A.

PB - Springer

ER -