Experimental Comparison Between Evolutionary Algorithm and Barycenter Heuristic for the Bipartite Drawing Problem | Science Publications

Journal of Computer Science

Z. Ezziane¹ 

关键词: Evolutionary algorithm;    edge crossing;    bipartite graph;    barycenter heuristic;    NP-complete problems;   

DOI  :  10.3844/jcssp.2007.717.722

学科分类：计算机科学（综合）

来源: Science Publications

【 摘 要 】

This research investigates the use of intelligent techniques for the bipartite drawing problem (BDP). Due to the combinatorial nature of the solution space, the use of traditional search methods lead to exponential time. Hence, the aim of this paper is to speed up the search time when solving the BDP through the use of Evolutionary Algorithms (EAs) and Barycenter Heuristic (BC). EA is applied on the BDP wherein genetic operators such as crossover and mutation are employed while searching for the best possible solution. The results show that the EA approach guides the search towards optimal solutions and in many instances it outperforms the BC.

【 授权许可】

Unknown