[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
  Logo Login | Create Account

The Steiner tree problem

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

[img] PDF
Download (1421Kb)


    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:
    Mentor / ComentorsIDFunction
    prof. dr. Matija CenceljMentor
    dr. Boštjan GabrovšekComentor
    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