A PROBE-Based Heuristic for Graph Partitioning

Chardaire, P., Barake, M. and McKeown, G. P. (2007) A PROBE-Based Heuristic for Graph Partitioning. IEEE Transactions on Computers, 56 (12). pp. 1701-1720. ISSN 0018-9340

Full text not available from this repository. (Request a copy)


A new heuristic algorithm, PROBE_BA, which is based on the recently introduced metaheuristic paradigm population- reinforced optimization-based exploration (PROBE), is proposed for solving the Graph Partitioning Problem. The "exploration" part of PROBE_BA is implemented by using the differential-greedy algorithm of Battiti and Bertossi and a modification of the Kernighan-Lin algorithm at the heart of Bui and Moon's genetic algorithm BFS _GBA. Experiments are used to investigate properties of PROBE and show that PROBE_BA compares favorably with other solution methods based on genetic algorithms, randomized reactive tabu search, or more specialized multilevel partitioning techniques. In addition, PROBE_BA finds new best cut values for 10 of the 34 instances in Walshaw's graph partitioning archive.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
Related URLs:
Depositing User: Vishal Gautam
Date Deposited: 07 Mar 2011 13:43
Last Modified: 21 Apr 2020 19:20
URI: https://ueaeprints.uea.ac.uk/id/eprint/23876
DOI: 10.1109/TC.2007.70760

Actions (login required)

View Item View Item