DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Optimal strategies in fractional games: vertex cover and domination
    Bujtás, Csilla ; Rote, Günter ; Tuza, Zsolt
    In a hypergraph ▫${\cal H}=(V,{\cal E})$▫ with vertex set ▫$V$▫ and edge set ▫${\cal E}$▫, a real-valued function ▫$f: V \to [0, 1]$▫ is a fractional transversal if ▫$\sum_{v\in E} f(v) \ge 1$▫ for ... every edge ▫$E \in {\cal E}$▫. Its size is ▫$|f| := \sum_{v \in V} f(v)$▫, and the fractional transversal number ▫$\tau^\ast({\cal H})$▫ is the smallest possible ▫$|f|$▫. We consider a game scenario where two players have opposite goals, one of them trying to minimize and the other to maximize the size of a fractional transversal constructed incrementally. We prove that both players have strategies to achieve their common optimum, and they can reach their goals using rational weights.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 24, no. 3, [article no.] P3.05, 2024, 19 str.)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2024
    Jezik - angleški
    COBISS.SI-ID - 202315011

    Povezava(-e):

    https://amc-journal.eu/index.php/amc/article/view/2771
    DOI

vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 24, no. 3, [article no.] P3.05, 2024, 19 str.)

loading ...
loading ...
loading ...

Vnos na polico