1.
Izbrane verzije dominacijskih množic in njihova časovna zahtevnostLučka Višnar, 2021, magistrsko delo
Opis: V tem magistrskem delu predstavimo različne dominacijske množice, in sicer popolno, učinkovito ter neodvisno.
V prvem delu so navedeni osnovni pojmi v teoriji grafov, vse potrebne definicije, izreki in trditve. V nadaljevanju predstavimo nekaj znanih NP-polnih problemov s področja dominacije na grafih in jih podkrepimo s primeri za namen dokazovanja časovne zahtevnosti. Za izbrane dominacijske probleme prikažemo kompleksnost odločitvenih problemov z dominacijskimi lastnostmi za glavne dominacijske množice (popolna, učinkovita in neodvisna) in druge izbrane dominacije. Nazadnje posežemo še po problemih popolnega dominacijskega števila za neodvisno, povezano in celotno dominacijo.
Ključne besede: dominacijska množica, popolna dominacijska množica, neodvisna dominacijska množica, učinkovita dominacijska množica, NP-polni problemi, dominacijsko število
Objavljeno v DKUM: 07.10.2021; Ogledov: 762; Prenosov: 32
Celotno besedilo (694,82 KB)
