VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • The median game
    Changat, Manoj, 1964- ...
    Vpeljana je igra za dva igralca ▫$I$▫ in ▫$II$▫ na grafu ▫$G$▫. Igralca izmenično izbirata vozlišča, dokler niso zasedena vsa vozlišča. Množico vozlišč, ki pripadajo igralcu ▫$I$▫ označimo s ... ▫$\Pi_I$▫ in tista, ki pripadajo igralcu ▫$II$▫, s ▫$\Pi_{II}$▫. Za ▫$d(x,\pi) = \sum_{y\in \pi}d(x,y)$▫ je ▫$M(\pi)=\min\{d(x,\pi)\,|\, x\in \pi\}$▫ medianska vrednost profila ▫$\pi\subseteq V(G)$▫. Cilj igralca ▫$I$▫ je maksimiziranje ▫$M(\pi_{II})-M(\pi_{I})$▫ in cilj igralca ▫$II$▫ je minimiziranje ▫$M(\pi_{II})-M(\pi_{I})$▫. Zmaga tisti, ki z manjšo mediansko vrednostjo svojega profila. Podan je potreben pogoj za drevo, ki omogoča igralcu ▫$I$▫ (ki začne z igro) zmagovalno strategijo. Pokažemo, da je igra izenačena na hiper kockah in nekaterih drugih simetričnih grafih. Obravnavani so tudi polni dvodelni grafi.
    Vir: Discrete optimization. - ISSN 1572-5286 (Vol. 17, 2015, str. 80-88)
    Vrsta gradiva - članek, sestavni del
    Leto - 2015
    Jezik - angleški
    COBISS.SI-ID - 17323865

    Povezava(-e):

    http://dx.doi.org/10.1016/j.disopt.2015.05.002

Vnos na polico