Using Helpful Sets to Improve Graph Bisections

We describe a new, linear time heuristic for the improvement of graph bisections. The method is a variant of local search with sophisticated neighborhood relations. It is based on graph-theoretic observations that were used to find upper bounds for the bisection width of regular graphs. Efficiently implemented, the new method can serve as an alternative to the commonly used local heuristics, not only in terms of the quality of attained solutions, but also in terms of space and time requirements. We compare our heuristic with a number of well known bisection algorithms. Extensive measurements show that the new method is a real improvement for graphs of certain types. Keywords: Graph Partitioning, Graph Bisection, Recursive Bisection, Edge Separators, Mapping, Local Search, Parallel Processing. This work was partly supported by the German Research Foundation (DFG Forschergruppe "Effiziente Nutzung massiv paralleler Systeme") and by the ESPRIT Basic Research Action No. 7141 (ALCOM II)...