Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin1029528330.pdf (454.53 KB)

ETD Abstract Container

Abstract Header

VISUALIZATION OF THE STEINER TREE HEURISTIC SOLUTIONS WITH LEDA

KO, MYUNG CHUL
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1029528330

Abstract Details

2002, MS, University of Cincinnati, Engineering : Computer Science.
Steiner tree problem can be summarized as finding the minimum cost subtree or subnetwork (minimum Steiner tree) spanning a subset of vertices identified as terminals in a network graph. In 1972, Karp proved that the Steiner tree problem is NP-complete problem for which no efficient polynomial time algorithm has been found [6]. Therefore, to find minimum Steiner tree all possible subtree including all the terminals should be found and the sum of the weights of the edges in each subtree should be calculated and compared. Since it requires exponential execution time based on problem size n and is hard to be done, heuristic algorithms, polynomial time algorithm, have been introduced to approximate the solution. The solutions obtained may not be optimal but expected to be reasonably close to minimum. Therefore, testing heuristic solutions with various prototypes of graph is necessary. In this thesis, first, a tool supporting visualization of Steiner tree problem heuristic solutions was implemented. The main purpose of the tool is to support efficient testing environment for heuristic solutions. In addition, it could support to design graph or network causing low cost Steiner tree. Since this tool uses graphic user interfaces, it is easy to verify correctness of a result obtained, create a test graph, and edit it by adding and deleting nodes and edges before and after applying a heuristic solution. The tool also allows user to save a result as an image and a text based data file and the data file can be used later as an input graph. Second, the performance of heuristics was compared. The purpose of performance comparison is to figure out how the performance of each heuristic is affected by a prototype of graphs represented by the number of nodes, edges, terminal (T), and connection degree in graphs. Five well-known heuristic solutions were implemented and applied to various test graphs. The detail of test result is introduced in Chapter 6. The tool was developed under Linux g++ compiler and LEDA library.
Dr. Fred Annexstein (Advisor)
Computer Science
Steiner tree problem; Heuristic solutions; LEDA

Recommended Citations

Citations

  • KO, M. C. (2002). VISUALIZATION OF THE STEINER TREE HEURISTIC SOLUTIONS WITH LEDA [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1029528330

    APA Style (7th edition)

  • KO, MYUNG. VISUALIZATION OF THE STEINER TREE HEURISTIC SOLUTIONS WITH LEDA. 2002. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1029528330.

    MLA Style (8th edition)

  • KO, MYUNG. "VISUALIZATION OF THE STEINER TREE HEURISTIC SOLUTIONS WITH LEDA." Master's thesis, University of Cincinnati, 2002. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1029528330

    Chicago Manual of Style (17th edition)

ucin1029528330
840
© 2002, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.