A genetic algorithm for determining the thickness of a graph

Authors
Makinen, E Poranen, T Vuorenmaa, P
Citation
E. Makinen et al., A genetic algorithm for determining the thickness of a graph, INF SCI, 138(1-4), 2001, pp. 155-164
Citations number
16
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION SCIENCES
ISSN journal
00200255 → ACNP
Volume
138
Issue
1-4
Year of publication
2001
Pages
155 - 164
Database
ISI
SICI code
0020-0255(200110)138:1-4<155:AGAFDT>2.0.ZU;2-U
Abstract
The thickness of a graph is the minimum number of planar subgraphs into whi ch the graph can be decomposed. Determining the thickness of a given graph is known to be an NP-complete problem. This paper discusses the possibility of determining the thickness of a graph using a genetic algorithm. Our tes ts show that the genetic approach outperforms the earlier heuristic algorit hms reported in the literature. (C) 2001 Elsevier Science Inc. All rights r eserved.