کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
473674 | 698804 | 2011 | 10 صفحه PDF | دانلود رایگان |
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.
Journal: Computers & Operations Research - Volume 38, Issue 7, July 2011, Pages 1066–1075