Problem 1-Steinerjevega drevesa

PREŠERN, SIMON (avtor), Fijavž, Gašper (mentor)

Problem 1-Steinerjevega drevesa je različica problema Steinerjevega drevesa, pri katerem pa smemo dodati zgolj eno dodatno točko. V delu podrobno opišemo učinkovit pristop Georgakopoulosa in Papadimitrouja k reševanju 1-Steinerjevega problema. Originalni Steinerjev problem je NP-težak. Po drugi strani je relativno enostavno videti, da je 1-Steinerjev problem polinomski. Z uporabo Dirichletovih diagramov, njihovih prekritij in učinkovitega računanja minimalnih vpetih dreves s preprocesiranjem pokažemo, da je moč 1-Steinerjevo drevo pri $n$ začetnih terminalih poiskati v času $O(n^2)$

• Jezik: Slovenski jezik
• Ključne besede: minimalno vpeto drevo, Steinerjev problem, 1-Steinerjev problem
• Vrsta gradiva: Diplomsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2019
• PID: 20.500.12556/RUL-111725
• COBISS.SI-ID: 1538416835
• Datum objave v RUL: 11.10.2019

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: The 1-Steiner tree problem

Izvleček

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.

• Ključne besede: minimum spanning tree, Steiner tree problem, 1-Steiner tree problem