The Steiner Tree Problem

Thumbnail Image

Files

Ala-Laurinaho_Vesa_2025.pdf (342.7 KB)

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025-08-21

Department

Major/Subject

Matematiikka ja systeemitieteet

Mcode

SCI3029

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

en

Pages

36

Series

Abstract

STEINER TREE refers to a family of optimisation problems, where the goal is to find the shortest network connecting a given set of terminals K. We define the Euclidean and Graph versions of the Steiner tree problem and show the corresponding methods for solving them. The first finite-time algorithm for the EUCLIDEAN STEINER TREE was presented by Melzak in 1961. The algorithm is old, and the goal of this thesis is to present this algorithm in modern terms and discuss some of the computational difficulties. In addition, we present the algorithm of Dreyfus and Wagner for the GRAPH STEINER TREE. The goal is to show that the GRAPH STEINER TREE is much faster to solve, which is an essential result for modern approximation algorithms of the EUCLIDEAN STEINER TREE. To illustrate the complexity of the algorithms, two simple examples are presented in the thesis.

Steiner-puu-ongelma viittaa joukkoon optimointiongelmia, joissa tavoitteena on löytää lyhyin verkko, joka yhdistää annetun joukon pisteitä K. Tässä työssä määritellään Steiner-puuongelma Euklidiselle tasolle ja verkolle, sekä esitetään algoritmit niiden ratkaisemiseen. Lisäksi algoritmien ratkaisemiseen vaadittavien laskutoimitusten lukumäärää arvioidaan. Vuonna 1961 Zdzislaw Alexander Melzak esitti ensimmäisen ratkaisualgoritmin Euklidiselle Steiner-puulle. Algoritmi esitellään tässä työssä käyttäen modernia termistöä ja geometrisiä rakenteita. Erityisesti halutaan osoittaa, että parhaan ratkaisun rakenteen valitseminen on haastavaa. Toinen työssä esiteltävä algoritmi on verkko-Steiner-puun ratkaiseva algoritmi, jonka Dreyfus ja Wagner esittivät vuonna 1972. Olennaisesti algoritmin ratkaisu-aika on exponentiaalinen joukon K pisteiden määrän suhteen, mutta polynominen verkon solmujen kokonaismäärän suhteen. Tavoitteena on osoittaa, että verkko-Steiner-puu on huomattavasti helpompi ratkaista kuin Euclidinen Steiner-puu. Tämä on keskeinen tulos likiarvojen löytämiselle moderneilla menetelmillä. Erityisesti polynominen kasvu suhteessa verkon solmujen määrään on hyödyllinen ominaisuus, koska käytännön ongelmissa pisteiden K osuus on pieni verkon kaikista solmuista. Työssä on esimerkit kummankin algoritmin käytöstä havainnollistamaan algoritmien toimintaa ja laskennan vaativuutta.

Description

Supervisor

Hollanti, Camilla

Thesis advisor

Kisfaludi-Bak, Sándor

Keywords

Steiner tree problem, euclidean Steiner tree, graph Steiner tree, Melzak’s algorithm

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202508266814

Collections

[kand] Perustieteiden korkeakoulu / SCI