Solving the Bipartite Subgraph Problem Using Genetic Algorithm with Conditional Genetic Operators

Bipartite subgraph problem is an important example of a class of combinatorial optimization problems. It has many important applications in modeling matching problem, modern coding theory, Communication network, and computer science. The goal of this NP-complete problem is to find a bipartite subgraph with maximum number of edges of the given graph. In this paper, for efficiently solving the problem, we propose a genetic algorithm-based approach in which the genetic operators are performed based on the condition instead of probability. The proposed algorithm is tested on a large number of instances, and the experimental results show that the proposed algorithm is superior to its competitors. (C) 2009 Institute of Electrical Engineers of Japan. Published by John Wiley & Soils, Inc.