A PROBE-based heuristic for graph partitioning

Pierre Chardaire, Musbah Barake, Geoff P. McKeown

Research output: Contribution to journalArticlepeer-review

34 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)1701-1720
Number of pages20
JournalIEEE Transactions on Computers
Issue number12
Publication statusPublished - 2007

Cite this