DocumentCode :
911917
Title :
A parallel improvement algorithm for the bipartite subgraph problem
Author :
Lee, Kuo Chun ; Funabiki, Nobuo ; Takefuji, Yoshiyasu
Author_Institution :
Cirrus Logic Inc., Fremont, CA, USA
Volume :
3
Issue :
1
fYear :
1992
fDate :
1/1/1992 12:00:00 AM
Firstpage :
139
Lastpage :
145
Abstract :
The authors propose the first parallel improvement algorithm using the maximum neural network model for the bipartite subgraph problem. The goal of this NP-complete problem is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that the algorithm finds a solution within 200 iteration steps and the solution quality is superior to that of the best existing algorithm. The algorithm is extended for the K-partite subgraph problem where no algorithm has been proposed
Keywords :
graph theory; iterative methods; neural nets; parallel algorithms; K-partite subgraph problem; NP-complete problem; bipartite subgraph problem; edges; iteration steps; maximum neural network model; parallel improvement algorithm; Artificial neural networks; Biological system modeling; Bipartite graph; Concurrent computing; Constraint optimization; Helium; Mathematical model; NP-complete problem; Neural networks; Neurons;
fLanguage :
English
Journal_Title :
Neural Networks, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9227
Type :
jour
DOI :
10.1109/72.105427
Filename :
105427
Link To Document :
بازگشت