GENETIC ALGORITHMS FOR DRAWING BIPARTITE GRAPHS

Authors
MAKINEN E SIERANTA M
Citation
E. Makinen et M. Sieranta, GENETIC ALGORITHMS FOR DRAWING BIPARTITE GRAPHS, International journal of computer mathematics, 53(3-4), 1994, pp. 157-166
Citations number
17
Categorie Soggetti
Computer Sciences",Mathematics
Journal title
International journal of computer mathematics
ISSN journal
00207160 → ACNP
Volume
53
Issue
3-4
Year of publication
1994
Pages
157 - 166
Database
ISI
SICI code
Abstract
This paper introduces genetic algorithms for the level permutation pro blem (LPP). The problem is to minimize the number of edge crossings in a bipartite graph when the order of vertices in one of the two vertex subsets is fixed. We show that genetic algorithms outperform the prev iously known heuristics especially when applied to low density graphs. Values for various parameters of genetic LPP algorithms are tested.