Solving the Graph Planarization Problem Using an Improved Genetic Algorithm

Rong-Long WANG  Kozo OKAZAKI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.5   pp.1507-1512
Publication Date: 2006/05/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.5.1507
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Numerical Analysis and Optimization
Keyword: 
graph planarization problem,  NP-complete problem,  genetic algorithm,  

Full Text: PDF>>
Buy this Article




Summary: 
An improved genetic algorithm for solving the graph planarization problem is presented. The improved genetic algorithm which is designed to embed a graph on a plane, performs crossover and mutation conditionally instead of probability. The improved genetic algorithm is verified by a large number of simulation runs and compared with other algorithms. The experimental results show that the improved genetic algorithm performs remarkably well and outperforms its competitors.