20.500.12556/DKUM-79865 Izbrane verzije dominacijskih množic in njihova časovna zahtevnost Selected versions of dominating sets and their time complexity 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. In this master's thesis we present different domination sets, that is perfect, efficient and independent perfect set. The first part lists the basic concepts in graph theory, all the necessary definitions, theorems and statements. In what follows we present some well known NP-complete problems and support them with examples for the purpose of proving time complexity. For selected domination problems, we show the complexity of decision problems with dominance properties for the main dominant sets (complete, efficient and independent) and for other selected dominant problems. Finally, we address the problems of perfect dominant number for independent, connected and total dominance. dominacijska množica popolna dominacijska množica neodvisna dominacijska množica učinkovita dominacijska množica NP-polni problemi dominacijsko število domination set perfect domination set independent domination set efficient domination set NP-complete problems domination number true true false [L. Višnar] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2021-08-20 09:52:43 2021-10-07 13:45:11 2022-08-09 22:09:36 0000-00-00 00:00:00 2021 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17:517.518.2(043.2) 78385923 MAG_Visnar_Lucka_2021.pdf MAG_Visnar_Lucka_2021.pdf 1 671AE52B2375872EFA6BE61A9AB00470 7b56fe02da0d60ec28f0efb6dbdc8aadc0700eb2682849ee0e251ca8119b8797 a9473c7c-018c-11ec-a02f-00155d581298 20.500.12556/dkum/3256a36f-d0de-40d0-b697-1a5227691338 https://dk.um.si/Dokument.php?lang=slv&id=151983 Fakulteta za naravoslovje in matematiko 0 0 0