<?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://dk.um.si/IzpisGradiva.php?id=46135"><dc:title>Hevristike za iskanje najmanjše dominantne množice</dc:title><dc:creator>Kajser,	Blaž	(Avtor)
	</dc:creator><dc:creator>Taranenko,	Andrej	(Mentor)
	</dc:creator><dc:subject>teorija grafov</dc:subject><dc:subject>dominantna množica</dc:subject><dc:subject>dominacijsko število</dc:subject><dc:subject>NP-poln problem</dc:subject><dc:subject>hevristike</dc:subject><dc:description>V problemu iskanja najmanjše dominantne množice imamo podan graf G, za katerega moramo poiskati najmanjšo podmnožico vozlišč, za katero velja, da predstavlja dominantno množico. V splošnem je problem NP-poln, zato za iskanje najmanjše dominantne množice uporabimo hevristike.
Magistrsko delo je sestavljeno iz štirih poglavij. V prvem poglavju so povzete osnovne definicije iz teorije grafov, ki jih v nadaljevanju potrebujemo za razumevanje magistrskega dela. Prav tako so v prvem poglavju definirane posebne družine grafov. V drugem poglavju sledi definicija dominantne množice in dokaz, da je odločitveni problem dominantne množice NP-poln problem. Predstavljene so tudi že znane zgornje in spodnje meje dominacijskega števila posameznih grafov. V naslednjem poglavju so predstavljene posamezne hevristike in njihova implementacija na problemu iskanja najmanjše dominantne množice v grafu. V zadnjem, četrtem poglavju pa so predstavljeni rezultati testiranja prej opisanih hevristik za problem najmanjše dominantne množice na kartezičnih, direktnih in krepkih produktih poti in ciklov.                        </dc:description><dc:publisher>[B. Kajser]</dc:publisher><dc:date>2014</dc:date><dc:date>2014-09-14 09:39:47</dc:date><dc:type>Magistrsko delo/naloga</dc:type><dc:identifier>46135</dc:identifier><dc:language>sl</dc:language></rdf:Description></rdf:RDF>