Premium
Solving the Bipartite Subgraph Problem Using Genetic Algorithm with Conditional Genetic Operators
Author(s) -
Chen ZhiQiang,
Wang RongLong,
Okazaki Kozo
Publication year - 2009
Publication title -
ieej transactions on electrical and electronic engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.254
H-Index - 30
eISSN - 1931-4981
pISSN - 1931-4973
DOI - 10.1002/tee.20459
Subject(s) - bipartite graph , induced subgraph isomorphism problem , matching (statistics) , genetic algorithm , coding (social sciences) , subgraph isomorphism problem , algorithm , computer science , mathematics , theoretical computer science , mathematical optimization , graph , line graph , statistics , voltage graph
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. Copyright © 2009 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.