Neural network for optimal steiner tree computation |
| |
Authors: | Chotipat Pornavalai Norio Shiratori Goutam Chakraborty |
| |
Affiliation: | (1) Research Institute of Electrical Communication, Tohoku University, 2-1-1 Katahira, Aoba-ku, 980 Sendai, Japan;(2) Software Center, The University of Aizu, Tsuruga, Ikki-Machi, 965-80 Aizu-Wakamatsu city, Japan |
| |
Abstract: | Hopfield neural network model for finding the shortest path between two nodes in a graph was proposed recently in some literatures. In this paper, we present a modified version of Hopfield model to a more general problem of searching an optimal tree (least total cost tree) from a source node to a number of destination nodes in a graph. This problem is called Steiner tree in graph theory, where it is proved to be a NP-complete. Through computer simulations, it is shown that the proposed model could always find an optimal or near-optimal valid solution in various graphs. |
| |
Keywords: | Steiner tree neural networks Hopfield model optimization |
本文献已被 SpringerLink 等数据库收录! |
|