Algorithm for solving bipartite subgraph problem with probabilistic self-organizing learning

Author

Choy, Cliflord Sze-Tsan ; Siu, Wan-chi

Author_Institution

Dept. of Electron. Eng., Hong Kong Polytech. Univ, Kowloon, Hong Kong

Volume

5

fYear

1995

fDate

9-12 May 1995

Firstpage

3351

Abstract

Self-organizing model has been successfully applied to solving some combinatorial optimization problems, including the travelling salesman problem, the routing problem and the cell-placement problem, but there has not much work reported on its application to solving the graph partitioning problem. We propose a novel mapping which has not been proposed before, with some changes to the original Kohonen´s (1982) algorithm so as to enable it to solve a partitioning problem-the bipartite subgraph problem. This new approach is compared with to the maximum neural network for solving the same problem, showing that the performance of our new approach is superior to that of the maximum neural network

Keywords

graph theory; optimisation; probability; self-organising feature maps; Kohonen´s algorithm; algorithm; bipartite subgraph problem; cell-placement problem; combinatorial optimization problems; graph partitioning problem solution; mapping; maximum neural network; performance; probabilistic self-organizing learning; routing problem; self-organizing model; travelling salesman problem; Councils; Hopfield neural networks; Motor drives; Neural networks; Neurons; Partitioning algorithms; Polynomials; Routing; Self organizing feature maps; Traveling salesman problems;

fLanguage

English

Publisher

ieee

Conference_Titel

Acoustics, Speech, and Signal Processing, 1995. ICASSP-95., 1995 International Conference on

Conference_Location

Detroit, MI

ISSN

1520-6149

Print_ISBN

0-7803-2431-5

Type

conf

DOI

10.1109/ICASSP.1995.479703

Filename

479703