20.500.12556/RUL-111725 Problem 1-Steinerjevega drevesa The 1-Steiner tree problem 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)$ 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. minimalno vpeto drevo Steinerjev problem 1-Steinerjev problem minimum spanning tree Steiner tree problem 1-Steiner tree problem true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2019-10-11 10:25:00 2019-10-11 10:25:03 2022-08-24 03:46:59 0000-00-00 00:00:00 2019 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 23329 1538416835 Presern_Simon_-_Problem_1-Steinerjevega_drevesa.pdf Presern_Simon_-_Problem_1-Steinerjevega_drevesa.pdf 1 6BEEB6721789FE2C13C6BEE859827C40 0cf25e59e1f00fc61b5195bef74a5c0944fc94102e4faad6d64a299acec4641a 773cdc02-a1b7-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=123623 Fakulteta za računalništvo in informatiko 0 0 0