Paper Info
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.
Year
DOI
Venue
2006
10.1007/11847250_2
IWPEC
Keywords
Field
DocType
cluster editing problem,linear programming,best result,practical implementation,cluster editing,straightforward greedy method,parameter tractable,interesting lack,linear program
Edit distance,Monotonic function,Algorithm,Greedy algorithm,Linear programming,Vertex cover,Binary search algorithm,Ramification (botany),Interleaving,Mathematics
Conference
Volume
ISSN
ISBN
4169
0302-9743
3-540-39098-7
Citations 
PageRank 
References 
32
1.58
11
Authors
6
Name
Order
Citations
PageRank
Frank K. H. A. Dehne11211146.07
Michael A. Langston21148137.59
Xuemei Luo3586.04
Sylvain Pitre41245.85
Peter Shaw5926.34
Yun Zhang61025.96