Problem 1-Steinerjevega drevesa

diplomsko delo

Simon Prešern (Avtor), Gašper Fijavž (Mentor)

Povzetek

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)$

Ključne besede

minimalno vpeto drevo;Steinerjev problem;1-Steinerjev problem;računalništvo;računalništvo in informatika;računalništvo in matematika;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2019
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[S. Prešern]
UDK:	51:004(043.2)
COBISS:	1538416835
Št. ogledov:	561
Št. prenosov:	185
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	The 1-Steiner tree problem
Sekundarni povzetek:	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.
Sekundarne ključne besede:	minimum spanning tree;Steiner tree problem;1-Steiner tree problem;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	40 str.
ID:	11242401