<?xml version="1.0"?>
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:dc="http://purl.org/dc/elements/1.1/"><rdf:Description rdf:about="https://repozitorij.uni-lj.si/IzpisGradiva.php?id=111725"><dc:title>Problem 1-Steinerjevega drevesa</dc:title><dc:creator>PREŠERN,	SIMON	(Avtor)
	</dc:creator><dc:creator>Fijavž,	Gašper	(Mentor)
	</dc:creator><dc:subject>minimalno vpeto drevo</dc:subject><dc:subject>Steinerjev problem</dc:subject><dc:subject>1-Steinerjev problem</dc:subject><dc:description>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)$</dc:description><dc:date>2019</dc:date><dc:date>2019-10-11 10:25:00</dc:date><dc:type>Diplomsko delo/naloga</dc:type><dc:identifier>111725</dc:identifier><dc:language>sl</dc:language></rdf:Description></rdf:RDF>