Tabu search for graph partitioning

In this paper, the authors develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. The authors compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.