Optimal strategies in fractional games: vertex cover and domination

Bujtás, Csilla (avtor), Rote, Günter (avtor), Tuza, Zsolt (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: fractional vertex cover, fractional transversal game, fractional domination game
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.01.2024
• Leto izida: 2024
• Št. strani: 19 str.
• Številčenje: Vol. 24, no. 3, article no. P3.05
• PID: 20.500.12556/RUL-166787
• UDK: 519.17
• ISSN pri članku: 1855-3966
• DOI: 10.26493/1855-3974.2771.4df
• COBISS.SI-ID: 202315011
• Datum objave v RUL: 24.01.2025

Gradivo je del revije

• Naslov: Ars mathematica contemporanea
• Založnik: Društvo matematikov, fizikov in astronomov, Društvo matematikov, fizikov in astronomov, Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
• ISSN: 1855-3966
• COBISS.SI-ID: 239049984

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.