diplomsko delo
Abstract
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).
Keywords
dominacijske igre na grafih;igralno dominacijsko število;časovna zahtevnost;prostorska zahtevnost;Turingovi stroji;PSPACE-polnost;POS-CNF problem;računalništvo in matematika;interdisciplinarni študij;univerzitetni študij;diplomske naloge;
Data
Language: |
Slovenian |
Year of publishing: |
2021 |
Typology: |
2.11 - Undergraduate Thesis |
Organization: |
UL FMF - Faculty of Mathematics and Physics |
Publisher: |
[M. Rajter] |
UDC: |
004:51(043.2) |
COBISS: |
82280451
|
Views: |
414 |
Downloads: |
51 |
Average score: |
0 (0 votes) |
Metadata: |
|
Other data
Secondary language: |
English |
Secondary title: |
Space complexity of graph domination games |
Secondary abstract: |
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). |
Secondary keywords: |
domination game on graphs;game domination number;time complexity;space complexity;Turing machines;PSPACE-completeness;POS- CNF problem;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Računalništvo;Univerzitetna in visokošolska dela; |
Type (COBISS): |
Bachelor thesis/paper |
Study programme: |
1000407 |
Thesis comment: |
Univ. v Ljubljani, Fak. za računalništvo in informatiko |
Pages: |
43 str. |
ID: |
13694374 |