A parallel multlevel metaheuristic for graph partitioning

A parallel multlevel metaheuristic for graph partitioning

0.00 Avg rating0 Votes
Article ID: iaor20043717
Country: Netherlands
Volume: 10
Issue: 3
Start Page Number: 315
End Page Number: 336
Publication Date: May 2004
Journal: Journal of Heuristics
Authors: , , ,
Keywords: heuristics, optimization: simulated annealing
Abstract:

One significant problem of optimisation which occurs in many scientific areas is that of graph partitioning. Several heuristics, which pertain to high quality partitions, have been put forward. Multilevel schemes can in fact improve the quality of the solutions. However, the size of the graphs is very large in many applications, making it impossible to effectively explore the search space. In these cases, parallel processing becomes a very useful tool overcoming this problem. In this paper, we propose a new parallel algorithm which uses a hybrid heuristic within a multilevel scheme. It is able to obtain very high quality partitions and improvement on those obtained by other algorithms previously put forward.

Reviews

Required fields are marked *. Your email address will not be published.