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.


Computer Science


This report is substantially the Ph.D. dissertation of the first author, completed December 1989.

Report Number


Document Type

Technical Report

Document Version

Final Version

File Type





© 1989 University of Missouri--Rolla, All rights reserved.

Publication Date

December 1989