Darja Prevc Mavrin (2017) *The Steiner tree problem*. MSc thesis.

PDF Download (1421Kb) |

## Abstract

The Steiner tree problem, named after a Swiss mathematician Jacob Steiner (1796–1863), is a problem that many mathematicians have been dealing with. His contribution, however, is unclear even to this day. The Steiner tree problem is searching for the shortest network with fixed number of points in the plane (this thesis focuses on the Euclidean plane), where points, which enable minimisation of the total length of the tree, can be added. These points are called the Steiner points. The Steiner ratio is the ratio between the length of the Steiner tree and the length of the minimal spanning tree. This thesis explanes the features of the Steiner tree and the exact and approximation algorithm used to solve the Steiner tree problem. Furthermore, it deals with the cases of the Steiner tree for three or four terminals, which are dependent on the positions of the terminals in the plane. The Steiner tree problem is not useful only in the mathematical world, but it can be also applied in the real world. For example, the traffic infrastructure.

Item Type: | Thesis (MSc thesis) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|

Keywords: | Euclidean plane, Steiner tree, Steiner point, minimum spanning tree, Steiner ratio, features of Steiner tree, exact algorithm, approximation algorithm | |||||||||

Number of Pages: | 62 | |||||||||

Language of Content: | Slovenian | |||||||||

Mentor / Comentors: |
| |||||||||

Link to COBISS: | http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=11655241) | |||||||||

Institution: | University of Ljubljana | |||||||||

Department: | Faculty of Education | |||||||||

Item ID: | 4587 | |||||||||

Date Deposited: | 18 Jul 2017 12:41 | |||||||||

Last Modified: | 18 Jul 2017 12:41 | |||||||||

URI: | http://pefprints.pef.uni-lj.si/id/eprint/4587 |

### Actions (login required)

View Item |