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

Translated title of the contribution: Neural network, Kernighan-Lin and multilevel heuristics for the Graph Bisection Problem on geometrically connected graphs

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

Research output: Contribution to journal › Article › peer-review

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.

Translated title of the contribution	Neural network, Kernighan-Lin and multilevel heuristics for the Graph Bisection Problem on geometrically connected graphs
Original language	Spanish
Pages (from-to)	97-100
Number of pages	4
Journal	Acta Cientifica Venezolana
Volume	60
Issue number	3
Publication status	Published - 2009
Externally published	Yes

ASJC Scopus subject areas

General Biochemistry,Genetics and Molecular Biology
General Environmental Science
General Agricultural and Biological Sciences

Cite this

@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

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this