Improved separators by multigrid methods

The graph partitioning problem has many different applications. One of them is the partitioning problem in parallel computations. With respect to process and device simulation we see two direct connections: (a) for some parallel solution methods we are interested in device simulation; good approximations of best separators are essential; (b) the equations to be solved here have properties pretty close to those of diffusion-convection equations-so the problem is a test case for the algebraic MG algorithm aimed at the device equations. The combinatorial problem is known to be NP hard-so different types of heuristic solutions are in use: stimulated annealing at the one end and the approximate solution of an analytic analog -the Neumann eigenvalue problem-at the other. By means of multigrid algorithms wider classes of problems, not only Neumann eigenvalue problems, can and will be efficiently solved. Therefore we are interested in more general analytic analogs, demonstrate the possibility to solve the related discrete problems and the potential of improvement.