Neural networks for solving constrained Steiner tree problem
Chotipat Pornavalai, Goutam Chakraborty, Norio Shiratori · 2002
A Hopfield neural network model for finding an optimal or shortest path between two nodes in a graph was proposed recently in some literature. In this paper, the authors present a modified version of the Hopfield model to find an optimal tree (least total cost tree) from a source node to a number of destination nodes, where each path from source to a destination must satisfy a constraint condition (delay bound condition). This problem is called the constrained Steiner tree (CST) problem, and was proved to be NP-complete. A new adaptive coefficient control method for the proposed Hopfield energy function is also developed. Through computer simulation it is shown that the proposed model could always find a near-optimal valid solution.