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

Gonzalo Hernandez, Jorge Cornejo, Roberto Leon, Luis Salinas

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.

Texto completo:

PDF


Creative Commons License
Todos los documentos publicados en esta revista se distribuyen bajo una
Licencia Creative Commons Atribución -No Comercial- Compartir Igual 4.0 Internacional.
Por lo que el envío, procesamiento y publicación de artículos en la revista es totalmente gratuito.