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.
