Abstract
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.
Recommended Citation
Osborne, Lawrence Joseph and Gillett, Billy E., "The Directed Steiner Problem on Graphs: A Simulated Annealing Approach" (1989). Computer Science Technical Reports. 92.
https://scholarsmine.mst.edu/comsci_techreports/92
Department(s)
Computer Science
Report Number
CSc-89-5
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1989 University of Missouri--Rolla, All rights reserved.
Publication Date
December 1989
Comments
This report is substantially the Ph.D. dissertation of the first author, completed December 1989.