Doctoral Dissertations

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"--Abstract, page iii.

Advisor(s)

Gillett, Billy E.

Committee Member(s)

Rigler, A. K.
Samaranayake, V. A.
Wilkerson, Ralph W.
Zobrist, George W. (George Winston), 1934-

Department(s)

Computer Science

Degree Name

Ph. D. in Computer Science

Publisher

University of Missouri--Rolla

Publication Date

Fall 1989

Pagination

xii, 193 pages

Note about bibliography

Includes bibliographical references (pages 179-192).

Rights

© 1989 Lawrence Joseph Osborne, All rights reserved.

Document Type

Dissertation - Open Access

File Type

text

Language

English

Thesis Number

T 5941

Print OCLC #

22039339

Download

Share

 
COinS