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

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

Resultado de la investigación: Contribución a una revista › Artículo › revisió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ón	Neural network, Kernighan-Lin and multilevel heuristics for the Graph Bisection Problem on geometrically connected graphs
Idioma original	Español
Páginas (desde-hasta)	97-100
Número de páginas	4
Publicación	Acta Cientifica Venezolana
Volumen	60
N.º	3
Estado	Publicada - 2009
Publicado de forma externa	Sí

Palabras clave

Graph bisection problem
Neural network

Áreas temáticas de ASJC Scopus

Bioquímica, genética y biología molecular (todo)
Ciencias ambientales (todo)
Agricultura y biología (todo)

Otros archivos y enlaces

Link to publication in Scopus

Citar esto

@article{9c9961c57b9c4d3d8cc444e10e67fd03,

title = "Heur{\'i}sticas de red neural, Kernighan-Lin y multinivel para el Problema de la Bisecci{\'o}n del Grafo en Grafos Conectados geom{\'e}tricamente",

abstract = "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.",

keywords = "Graph bisection problem, Neural network",

author = "Gonzalo Hern{\'a}ndez and Jorge Cornejo and Roberto Le{\'o}n and Luis Salinas",

year = "2009",

language = "Espa{\~n}ol",

volume = "60",

pages = "97--100",

journal = "Acta Cientifica Venezolana",

issn = "0001-5504",

publisher = "Edificio FundaVAC - AsoVAC",

number = "3",

}

TY - JOUR

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

AU - Hernández, Gonzalo

AU - Cornejo, Jorge

AU - León, Roberto

AU - Salinas, Luis

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - Graph bisection problem

KW - Neural network

UR - http://www.scopus.com/inward/record.url?scp=84874710239&partnerID=8YFLogxK

M3 - Artículo

AN - SCOPUS:84874710239

SN - 0001-5504

VL - 60

SP - 97

EP - 100

JO - Acta Cientifica Venezolana

JF - Acta Cientifica Venezolana

IS - 3

ER -

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

Resumen

Palabras clave

Áreas temáticas de ASJC Scopus

Otros archivos y enlaces

Huella

Citar esto