20.500.12556/RUL-132122 Prostorska zahtevnost grafovskih dominacijskih iger Space complexity of graph domination games V nalogi obravnavamo dominacijske igre na grah, njihove različice in igralno dominacijsko število, ki je število potez v poteku dominacijske igre, v kateri oba igralca igrata optimalno. Ukvarjamo se s prostorsko zahtev- nostjo izračuna igralnega dominacijskega števila. Pokažemo, da je igralno dominacijsko število možno izračunati z algoritmom, ki ima linearno pro- storsko zahtevnost, kar pomeni, da je problem v razredu PSPACE. Končno dokažemo, da je problem dominacijskih iger na grah PSPACE-poln za pre- vedbe v polinomskem času. To storimo s sklicevanjem na PSPACE-polnost problema zmagovalca igre na izjavnih formulah v konjuktivni obliki brez ne- gacij (POS-CNF). We consider domination games on graphs, their variants and the game domination number, which is the number of moves made in a graph domi- nation game assuming both players play optimally. We deal with the space complexity the game domination number. We show that the game domina- tion number can be calculated with an algorithm that runs in linear space complexity, which means that the problem is in PSPACE. Finally, we prove that the domination game on graphs problem is PSPACE-complete under polynomial time reductions. We do that using the PSPACE-completeness of the game problem on propositional formulas in conjunctive normal form without negations (POS-CNF). Dominacijske igre na grah Igralno dominacijsko število Časovna zahtevnost Prostorska zahtevnost Turingovi stroji PSPACE-polnost POS-CNF problem. Domination game on graphs Game domination number Time complexity Space complexity Turing machines PSPACE-completeness POS- CNF problem. true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2021-10-13 12:05:05 2021-10-13 12:05:09 2023-12-01 10:02:54 0000-00-00 00:00:00 2021 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 33001 82280451 Rajter_Miha_-_Prostorska_zahtevnost_grafovskih_dominacijskih_iger.pdf Rajter_Miha_-_Prostorska_zahtevnost_grafovskih_dominacijskih_iger.pdf 1 8EEE1E1D184654818763BEB1AAA2F56D 867e1e9b41ef5f47591aaff5a9f07448b4d95b419dc77b9452ba1646f73a1f24 0bfe1915-2c0d-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=149653 Fakulteta za računalništvo in informatiko Fakulteta za matematiko in fiziko 0 0 0