diplomsko delo
Miha Rajter (Author), Martin Raič (Mentor)

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:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FMF - Faculty of Mathematics and Physics
Publisher: [M. Rajter]
UDC: 004:51(043.2)
COBISS: 82280451 Link will open in a new window
Views: 414
Downloads: 51
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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