FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • The game total domination problem is log-complete in PSPACE
    Brešar, Boštjan ; Henning, Michael A.
    V članku nadaljujemo obravnavo celotne dominacijske igre v grafih, ki so jo vpeljali Henning in soavtorji leta 2015. Vozlišče grafa ▫$G$▫ celotno dominira neko drugo vozlišče tega grafa, ko je z njim ... sosednje. Celotna dominantna množica grafa ▫$G$▫ je takšna množica njegovih vozlišč ▫$S$▫, za katero je vsako vozlišče grafa ▫$G$▫ celotno dominirano s strani kakega vozlišča množice ▫$S$▫. Celotno dominacijsko igro na grafu ▫$G$▫ igrata dva igralca, Dominator in Zavlačevalka, ki se izmenjujeta v potezah; poteza je izbira vozlišča, ki celotno dominira vsaj eno vozlišče, ki pred to izbiro še ni bilo celotno dominirano s strani predhodno izbranih vozlišč. Igra se konča, ko je množica izbranih vozlišč celotna dominantna množica grafa ▫$G$▫. Dominatorjev cilj je končati igro v najmanjšem možnem številu potez, medtem ko želi Zavlačevalka igro razvleči tako, da bo izbranih čim več vozlišč. Igralno celotno dominantno število grafa ▫$G$▫ je število izbranih vozlišč v igri, ki jo začne Dominator in v kateri oba igralca igrata optimalno glede na njuna cilja. V članku dokažemo, da je preverba, ali je igralno celotno dominantno število grafa navzgor omejeno z danim naravnim številom, log-poln problem v razredu PSPACE.
    Vir: Information processing letters. - ISSN 0020-0190 (Vol. 126, 2017, str. 12-17)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2017
    Jezik - angleški
    COBISS.SI-ID - 18051417

    Povezava(-e):

    http://dx.doi.org/10.1016/j.ipl.2017.05.007
    DOI

Vnos na polico