Neural network, kernighan-lin and multilevel heuristics for the graph bisection problem on geometrically connected graphs

Resumen

A neural network heuristic for the Graph Bisection Problem is studied numerically on geometrically connected graphs and its performance is compared with the Kernighan - Lin (KL) and Multilevel (ML) heuristics. For mediumscale sparse graphs with n = 2000 to n = 12000 nodes it was obtained that the NN heuristic applied to the Graph Bisection Problem present a greedy behaviour in comparison to other local improvements heuristics: Kernighan-Lin, Multilevel. The experimental results for large graphs recommend to use KL as partitioning heuristic for sparse geometrically connected graphs.