<?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=171661"><dc:title>Modeliranje in reševanje problema drevesne širine s SAT</dc:title><dc:creator>Stojanovski,	Andrej	(Avtor)
	</dc:creator><dc:creator>Čibej,	Uroš	(Mentor)
	</dc:creator><dc:subject>drevesna širina</dc:subject><dc:subject>SAT</dc:subject><dc:subject>grafi</dc:subject><dc:subject>NP-polni problemi</dc:subject><dc:subject>drevesna dekompozicija</dc:subject><dc:description>V diplomski nalogi obravnavamo problem določanja drevesne širine grafa, ki ima pomembno vlogo pri reševanju veliko NP-polnih kombinatoričnih problemov na grafih. Predstavimo nov pristop, kjer problem drevesne širine kodiramo kot SAT-primere in ga rešujemo s sodobnimi SAT reševalniki. Nato opišemo postopek kodiranja ter izvedemo obsežno primerjalno analizo SAT pristopa z drugimi natančnimi in hevrističnimi metodami (PID-BT, CopsAndRobber, QuickBB). Eksperimenti na standardnih in naključno generiranih grafih nam pokažejo, da SAT pristop dosega konkurenčne rezultate na manjših in srednje velikih primerih, hkrati pa omogoča preverjanje optimalnosti hevrističnih rešitev.</dc:description><dc:date>2025</dc:date><dc:date>2025-08-29 13:25:02</dc:date><dc:type>Diplomsko delo/naloga</dc:type><dc:identifier>171661</dc:identifier><dc:language>sl</dc:language></rdf:Description></rdf:RDF>