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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
S. Cavalieri, “Optimal path determination in a graph by hopfield neural network”, Neural Networks, Vol. 7, No. 2, pp. 397–404, 1994.
M. K. Mehmet and F. Kamoun, “Neural networks for shortest path computation and routing in computer networks”, IEEE Trans. on Neural Network, Vol. 4, No. 6, pp. 941–954, 1993.
L. Kou, G. Markowsky and L. Berman, “A fast algorithm for steiner trees”, Acta Informatica, 15: 141–145, 1981.
R. Widyono, “The design and evaluation of routing algorithms for real-time channels”, Technical Report TR-94-024, International Computer Science Institute, Berkeley, June 1994.
C. Pornavalai, G. Chakraborty and N. Shiratori, “Neural networks for solving constrained steiner tree problem”, in 1995 IEEE Int. Conf. on Neural Networks (ICNN'95), Perth Australia, November 1995.
D. W. Tank and J. Hopfield, “Simple neural optimization networks: an a/d converter, signal decision circuit, and a linear programming circuit” IEEE Trans on Circuits and Systems, Vol. 33, No. 5, pp. 533–541, 1986.
M. W. Dixon, G. R. Cole and M. I. Bellgard, “Using the hopfield neural network with mean field annealing to solve the shortest path problem in a communication network”, in 1995 IEEE Int. Conf. on Neural Networks (ICNN'95), Perth Australia, November 1995.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Pornavalai, C., Shiratori, N. & Chakraborty, G. Neural network for optimal steiner tree computation. Neural Process Lett 3, 139–149 (1996). https://doi.org/10.1007/BF00420283
Issue Date:
DOI: https://doi.org/10.1007/BF00420283