Abstract:
Recent advances in exact algorithm design and multi-processor industry have led to
an increasing interest in exact (or optimal) solutions for hard problems. This interest
was also motivated by the emergence of parameterized complexity theory as well
as the recent discouraging hardness of approximation results for most intractable
problems. Coupling the best exact algorithms with scalable parallel implementations
is a promising approach for dealing with computationally demanding problems. In this
work, we introduce a parallel technique for solving the Maximum Clique problem using
clusters of multi-core machines. Our algorithm employs a scalable load balancing
strategy that is based on dynamic search-tree decomposition. We present experimental
results that verify the scalability of our technique and its utility as a better alternative
to approximation algorithms in many practical applications.
