In iterative improvement partitioning algorithms, tie-breaking in the choice of maximum-gain vertices has a great impact on the performance. We propose a new tie-breaking strategy in an iterative improvement algorithm for graph partitioning. The proposed method is simple but nevertheless performed better than other traditional techniques.
Yoon, Yourim and Kim, Yong-Hyuk
"New Bucket Managements in Iterative Improvement Partitioning Algorithms,"
Applied Mathematics & Information Sciences: Vol. 07
, Article 13.
Available at: https://dc.naturalspublishing.com/amis/vol07/iss2/13