Language: | Slovenian |
---|---|
Year of publishing: | 2019 |
Typology: | 2.11 - Undergraduate Thesis |
Organization: | UL FRI - Faculty of Computer and Information Science |
Publisher: | [S. Prešern] |
UDC: | 51:004(043.2) |
COBISS: | 1538416835 |
Views: | 561 |
Downloads: | 185 |
Average score: | 0 (0 votes) |
Metadata: |
Secondary language: | English |
---|---|
Secondary title: | The 1-Steiner tree problem |
Secondary abstract: | The 1-Steiner tree problem is a variant of the Steiner tree problem, where we are only allowed to use a single additional point. In this thesis we present an efficient approach of Georgakopoulos and Papadimitrou to solving the 1-Steiner tree problem. The original Steiner tree problem is known to be NP-hard. On the other hand it is fairly easy to show that the 1-Steiner tree problem is polynomial. With the use of Dirichlet diagrams, their overlay, and an efficient updating of minimal spanning trees with preprocessing we show, that the 1-Steiner tree of a set of $n$ terminals can be computed in $O(n^2)$ time. |
Secondary keywords: | minimum spanning tree;Steiner tree problem;1-Steiner tree problem;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma; |
Type (COBISS): | Bachelor thesis/paper |
Study programme: | 1000407 |
Embargo end date (OpenAIRE): | 1970-01-01 |
Thesis comment: | Univ. v Ljubljani, Fak. za računalništvo in informatiko |
Pages: | 40 str. |
ID: | 11242401 |