Improved search-tree algorithms for the cluster edit problem. (c2011)
Ali Kassem Ghrayeb · 2011
In the Cluster Edit problem, we are asked to transform a given graph into a transitive graph, via edge deletion or addition operations, to make sure that the vertices are partitioned into a disjoint union of cliques.Cluster Edit finds application in a number of domains, including computational biology and social networks.When parameterized by the number of permitted edge-edit operation (k), the problem can be solved in O (3 k ) time via a search-tree backtracking strategy.The current fastest worstcase fixed-parameter algorithm described in [7] adopts the same strategy and solves Cluster Edit in O (1.82 k ).This thesis presents new techniques to enhance any search tree-based algorithm for the Cluster Edit problem.These techniques, which include new heuristics and impose bounds on allowable edge operations per vertex, cause effective pruning of search-trees and yield noticeable improvements in experimental running times on almost all types of input instances.