Artificial neural networks for the bipartite and k-partite subgraph problems

Jenn Shiang Lai; Young Ja Ko; Sy Yen Kuo

doi:10.1007/3-540-56891-3_34

Artificial neural networks for the bipartite and k-partite subgraph problems

Jenn Shiang Lai
, Young Ja Ko
, Sy Yen Kuo

National Taiwan University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In [1], Lee, Funabiki and Takefuji proposed a parallel algorithm for solving the bipartite subgraph problem with the maximum neural networks. In this paper, we present a new algorithm based on the discrete Hopfield network to deal with the same problem. Compared with the previous maximum neural network algorithm, our method can find solutions of same quality or better with half of neurons and much less computation time. Furthermore, for the general K-partite subgraph problem, a novel interactive Hopfield network system is devised to solve it effectively. The algorithm has been implemented and the experimental results indeed demonstrate the effectiveness of our approach.

Original language	English
Title of host publication	PARLE 1993 - Parallel Architectures and Languages Europe - 5th International PARLE Conference, Proceedings
Editors	Arndt Bode , Mike Reeve , Gottfried Wolf
Publisher	Springer Verlag
Pages	426-437
Number of pages	12
ISBN (Print)	9783540568919
DOIs	https://doi.org/10.1007/3-540-56891-3_34
State	Published - 1993
Externally published	Yes
Event	5th International Conference on Parallel Architectures and Languages Europe, PARLE 1993 - Munich, Germany Duration: 14 06 1993 → 17 06 1993

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	694 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th International Conference on Parallel Architectures and Languages Europe, PARLE 1993
Country/Territory	Germany
City	Munich
Period	14/06/93 → 17/06/93

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.

Access to Document

10.1007/3-540-56891-3_34

Cite this

Lai, J. S., Ko, Y. J., & Kuo, S. Y. (1993). Artificial neural networks for the bipartite and k-partite subgraph problems. In A. Bode , M. Reeve , & G. Wolf (Eds.), PARLE 1993 - Parallel Architectures and Languages Europe - 5th International PARLE Conference, Proceedings (pp. 426-437). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 694 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-56891-3_34

Lai, Jenn Shiang ; Ko, Young Ja ; Kuo, Sy Yen. / Artificial neural networks for the bipartite and k-partite subgraph problems. PARLE 1993 - Parallel Architectures and Languages Europe - 5th International PARLE Conference, Proceedings. editor / Arndt Bode ; Mike Reeve ; Gottfried Wolf . Springer Verlag, 1993. pp. 426-437 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5aa967a920e94f90a7091ec68ddce851,

title = "Artificial neural networks for the bipartite and k-partite subgraph problems",

abstract = "In [1], Lee, Funabiki and Takefuji proposed a parallel algorithm for solving the bipartite subgraph problem with the maximum neural networks. In this paper, we present a new algorithm based on the discrete Hopfield network to deal with the same problem. Compared with the previous maximum neural network algorithm, our method can find solutions of same quality or better with half of neurons and much less computation time. Furthermore, for the general K-partite subgraph problem, a novel interactive Hopfield network system is devised to solve it effectively. The algorithm has been implemented and the experimental results indeed demonstrate the effectiveness of our approach.",

author = "Lai, \{Jenn Shiang\} and Ko, \{Young Ja\} and Kuo, \{Sy Yen\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 5th International Conference on Parallel Architectures and Languages Europe, PARLE 1993 ; Conference date: 14-06-1993 Through 17-06-1993",

year = "1993",

doi = "10.1007/3-540-56891-3\_34",

language = "英语",

isbn = "9783540568919",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "426--437",

editor = "\{Bode \}, Arndt and \{Reeve \}, Mike and \{Wolf \}, Gottfried",

booktitle = "PARLE 1993 - Parallel Architectures and Languages Europe - 5th International PARLE Conference, Proceedings",

address = "德国",

}

Lai, JS, Ko, YJ & Kuo, SY 1993, Artificial neural networks for the bipartite and k-partite subgraph problems. in A Bode , M Reeve & G Wolf (eds), PARLE 1993 - Parallel Architectures and Languages Europe - 5th International PARLE Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 694 LNCS, Springer Verlag, pp. 426-437, 5th International Conference on Parallel Architectures and Languages Europe, PARLE 1993, Munich, Germany, 14/06/93. https://doi.org/10.1007/3-540-56891-3_34

Artificial neural networks for the bipartite and k-partite subgraph problems. / Lai, Jenn Shiang; Ko, Young Ja; Kuo, Sy Yen.
PARLE 1993 - Parallel Architectures and Languages Europe - 5th International PARLE Conference, Proceedings. ed. / Arndt Bode ; Mike Reeve ; Gottfried Wolf . Springer Verlag, 1993. p. 426-437 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 694 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Artificial neural networks for the bipartite and k-partite subgraph problems

AU - Lai, Jenn Shiang

AU - Ko, Young Ja

AU - Kuo, Sy Yen

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1993.

PY - 1993

Y1 - 1993

N2 - In [1], Lee, Funabiki and Takefuji proposed a parallel algorithm for solving the bipartite subgraph problem with the maximum neural networks. In this paper, we present a new algorithm based on the discrete Hopfield network to deal with the same problem. Compared with the previous maximum neural network algorithm, our method can find solutions of same quality or better with half of neurons and much less computation time. Furthermore, for the general K-partite subgraph problem, a novel interactive Hopfield network system is devised to solve it effectively. The algorithm has been implemented and the experimental results indeed demonstrate the effectiveness of our approach.

AB - In [1], Lee, Funabiki and Takefuji proposed a parallel algorithm for solving the bipartite subgraph problem with the maximum neural networks. In this paper, we present a new algorithm based on the discrete Hopfield network to deal with the same problem. Compared with the previous maximum neural network algorithm, our method can find solutions of same quality or better with half of neurons and much less computation time. Furthermore, for the general K-partite subgraph problem, a novel interactive Hopfield network system is devised to solve it effectively. The algorithm has been implemented and the experimental results indeed demonstrate the effectiveness of our approach.

UR - https://www.scopus.com/pages/publications/85029651357

U2 - 10.1007/3-540-56891-3_34

DO - 10.1007/3-540-56891-3_34

M3 - 会议稿件

AN - SCOPUS:85029651357

SN - 9783540568919

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 426

EP - 437

BT - PARLE 1993 - Parallel Architectures and Languages Europe - 5th International PARLE Conference, Proceedings

A2 - Bode , Arndt

A2 - Reeve , Mike

A2 - Wolf , Gottfried

PB - Springer Verlag

T2 - 5th International Conference on Parallel Architectures and Languages Europe, PARLE 1993

Y2 - 14 June 1993 through 17 June 1993

ER -

Lai JS, Ko YJ, Kuo SY. Artificial neural networks for the bipartite and k-partite subgraph problems. In Bode A, Reeve M, Wolf G, editors, PARLE 1993 - Parallel Architectures and Languages Europe - 5th International PARLE Conference, Proceedings. Springer Verlag. 1993. p. 426-437. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-56891-3_34

Artificial neural networks for the bipartite and k-partite subgraph problems

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this