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 graphtheoretic 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 be 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.