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

Povzetek

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).

Ključne besede

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;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
Založnik: [M. Rajter]
UDK: 004:51(043.2)
COBISS: 82280451 Povezava se bo odprla v novem oknu
Št. ogledov: 414
Št. prenosov: 51
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Space complexity of graph domination games
Sekundarni povzetek: 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).
Sekundarne ključne besede: 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;
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000407
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 43 str.
ID: 13694374