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

Sze Tsan Choy; Wan Chi Siu

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

Research output: Journal article publication › Conference article › Academic research › peer-review

Abstract

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

Original language	English
Pages (from-to)	3351-3354
Number of pages	4
Journal	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume	5
Publication status	Published - 1 Jan 1995
Event	Proceedings of the 1995 20th International Conference on Acoustics, Speech, and Signal Processing. Part 2 (of 5) - Detroit, MI, United States Duration: 9 May 1995 → 12 May 1995

ASJC Scopus subject areas

Software
Signal Processing
Electrical and Electronic Engineering

Cite this

@article{e5d1950aca1440f7b04eb4d94a5dc13b,

title = "Algorithm for solving bipartite subgraph problem with probabilistic self-organizing learning",

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

author = "Choy, {Sze Tsan} and Siu, {Wan Chi}",

year = "1995",

month = jan,

day = "1",

language = "English",

volume = "5",

pages = "3351--3354",

journal = "Proceedings - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing",

issn = "0736-7791",

publisher = "IEEE",

note = "Proceedings of the 1995 20th International Conference on Acoustics, Speech, and Signal Processing. Part 2 (of 5) ; Conference date: 09-05-1995 Through 12-05-1995",

}

TY - JOUR

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

AU - Choy, Sze Tsan

AU - Siu, Wan Chi

PY - 1995/1/1

Y1 - 1995/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=0028996603&partnerID=8YFLogxK

M3 - Conference article

VL - 5

SP - 3351

EP - 3354

JO - Proceedings - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing

JF - Proceedings - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing

SN - 0736-7791

T2 - Proceedings of the 1995 20th International Conference on Acoustics, Speech, and Signal Processing. Part 2 (of 5)

Y2 - 9 May 1995 through 12 May 1995

ER -

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

Abstract

ASJC Scopus subject areas

Other files and links

Cite this