#TITLE_ALTERNATIVE#
Steiner tree is one of the topics in Graph Theory which is widely used for constructing an efficient network. In this final project, an application to find a Steiner tree in a particular network is developed. This application is implemented to find a gas pipeline network in Java Island which connect...
Saved in:
| Main Author: | |
|---|---|
| Format: | Final Project |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/9779 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | Steiner tree is one of the topics in Graph Theory which is widely used for constructing an efficient network. In this final project, an application to find a Steiner tree in a particular network is developed. This application is implemented to find a gas pipeline network in Java Island which connects all cities that have gas or fuel depot with minimum length. In addition, the application also considers topographical factor (height difference). The topographical factor should be considered since Java Island has various height differences. Heuristic developed by Markowsky et al is used for constructing the network in this final project. The algorithm is chosen based on its faster running time compared with algorithm that search Steiner tree by using brute force search to check all possibilities of minimal spanning tree, the weight of a Steiner tree produced by the heuristic algorithm may not be the minimum weight, however this weight will not exceeds a particular upper bound. |
|---|