Heurísticas de red neural, Kernighan-Lin y multinivel para el Problema de la Bisección del Grafo en Grafos Conectados geométricamente

Gonzalo Hernández, Jorge Cornejo, Roberto León, Luis Salinas

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

Resumen

A neural network (NN) 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 medium-scale sparse graphs with n = 2000 to n = 12000 nodes, the NN heuristic applied to the Graph Bisection Problem presents a greedy behavior in comparison to other local improvements heuristics, namely Kernighan-Lin and Multilevel. The experimental results for large graphs recommend the use of KL as the partitioning heuristic for sparse geometrically connected graphs.

Título traducido de la contribuciónNeural network, Kernighan-Lin and multilevel heuristics for the Graph Bisection Problem on geometrically connected graphs
Idioma originalEspañol
Páginas (desde-hasta)97-100
Número de páginas4
PublicaciónActa Cientifica Venezolana
Volumen60
N.º3
EstadoPublicada - 2009
Publicado de forma externa

Palabras clave

  • Graph bisection problem
  • Neural network

Áreas temáticas de ASJC Scopus

  • Bioquímica, Genética y Biología Molecular General
  • Ciencias Ambientales General
  • Ciencias Agrícolas y Biológicas General

Huella

Profundice en los temas de investigación de 'Heurísticas de red neural, Kernighan-Lin y multinivel para el Problema de la Bisección del Grafo en Grafos Conectados geométricamente'. En conjunto forman una huella única.

Citar esto