A parallel improvement algorithm for the bipartite subgraph problem
- 1 January 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 3 (1) , 139-145
- https://doi.org/10.1109/72.105427
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 proposedKeywords
This publication has 11 references indexed in Scilit:
- A parallel algorithm for allocation of spare cells on memory chipsIEEE Transactions on Reliability, 1991
- Artificial neural networks for four-coloring map problems and K-colorability problemsIEEE Transactions on Circuits and Systems, 1991
- Highly Parallel ComputationScience, 1990
- A parallel algorithm for tiling problemsIEEE Transactions on Neural Networks, 1990
- Parallel algorithms for finding a near-maximum independent set of a circle graphIEEE Transactions on Neural Networks, 1990
- A Near-Optimum Parallel Planarization AlgorithmScience, 1989
- Largest bipartite subgraphs in triangle‐free graphs with maximum degree threeJournal of Graph Theory, 1986
- On some weakly bipartite graphsOperations Research Letters, 1983
- Minimum-Via Topological RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983
- A logical calculus of the ideas immanent in nervous activityBulletin of Mathematical Biology, 1943