Article ID Journal Published Year Pages File Type
473674 Computers & Operations Research 2011 10 Pages PDF
Abstract

Graph partitioning is one of the fundamental NP-complete problems which is widely applied in many domains, such as VLSI design, image segmentation, data mining, etc. Given a graph G=(V,E), the balanced k-partitioning problem consists in partitioning the vertex set V into k disjoint subsets of about the same size, such that the number of cutting edges is minimized. In this paper, we present a multilevel algorithm for balanced partition, which integrates a powerful refinement procedure based on tabu search with periodic perturbations. Experimental evaluations on a wide collection of benchmark graphs show that the proposed approach not only competes very favorably with the two well-known partitioning packages METIS and CHACO, but also improves more than two thirds of the best balanced partitions ever reported in the literature.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, ,