This page shows the best results reported in the following paper:
Una Benlic and Jin-Kao Hao. An Effective Multilevel Tabu Search Approach for Balanced Graph
Partitioning. Computers
&
Operations Research 38(7): 1066-1075, 2011.
Table1. Best results obtained by Multilevel Iterative Tabu Search (MITS) algorithm in the paper above for number of subsets k set to 2, 4, 8, 16, 32 and 64
Notes:
- The benchmark graphs are available at the Graph Partitioning Archive http://staffweb.cms.gre.ac.uk/~wc06/partition/, together with the best known up-to-date results reported in the litterature.
- The output format is a string of size |V|, such that the ith element corresponds to the subset of vertex i.
- Except for several cases, the partitions provided in Table 1 are balanced. The partition imbalance of imbalanced partitions is indicated in parentheses.