Improved search-tree algorithms for the cluster edit problem. (c2011)

Abstract

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 (3k) 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.82k). 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.