IEEE Journal on Selected Areas in Communications · 1997 · 86 citations · 27 references
ComputingComputer ScienceComputer NetworksDistributed SystemsInterconnection NetworksCommunication NetworksDistributed ComputingNetwork OptimizationNetwork TopologyRoutingRouting AlgorithmsAsynchronous Transfer ModeHeuristicsMinimum Spanning Tree ConstructionMinimum Spanning Tree ProblemMulticast RoutingSpanning Tree ConstructionSteiner Tree ApproximationSteiner Tree Problem
Future networks must be adequately equipped to handle multipoint communication in a fast and economical manner. Services requiring such support include desktop video conferencing, tele-classrooms, distributed database applications, etc. In networks employing the asynchronous transfer mode (ATM) technology, routing a multicast is achieved by constructing a minimum cost tree that spans the source and all the destinations. When the network is modeled as a weighted, undirected graph, the problem is that of finding a minimal Steiner tree for the graph, given a set of destinations. The problem is known to be NP-complete. Consequently, several heuristics exist which provide approximate solutions to the Steiner problem in networks, We show how the random neural network (RNN) can be used to significantly improve the quality of the Steiner trees delivered by the best available heuristics which are the minimum spanning tree heuristic and the average distance heuristic. We provide an empirical comparison and find that the heuristics which are modified using the neural network yield significantly improved trees.
27
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Routing of multipoint connections
Bernard M. Waxman · IEEE Journal on Selected Areas in Communications · 1988 · 2.9K citations
A fast algorithm for Steiner trees
Lawrence T. Kou, George Markowsky, L. Berman · Acta Informatica · 1981 · 1.2K citations
E. N. Gilbert, H. O. Pollak · SIAM Journal on Applied Mathematics · 1968 · 938 citations