The well-known Steiner Problem on Graphs is an NP-complete problem for which there are many heuristic and exact algorithms that are deterministic. In this dissertation a new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing. A version of annealing is developed for the Directed Steiner Problem and compared with one of the best general annealing schemes. Then a comparison is made between simulated annealing and the traditional branch and bound technique. The dual ascent algorithm of Richard T. Wong is used to obtain lower bounds for the branch and bound scheme. It appears that for random graphs with more than approximately 60 vertices the new method is on the average superior in finding near-optimum answers quickly. In fact, for large values of N, where N is the number of vertices, it is possible to obtain answers within a few percent of the optimum in polynomial time.
Osborne, Lawrence Joseph and Gillett, Billy E., "The Directed Steiner Problem on Graphs: A Simulated Annealing Approach" (1989). Computer Science Technical Reports. 92.
© 1989 University of Missouri--Rolla, All rights reserved.