| Title: | Optimal strategies in fractional games: vertex cover and domination |
|---|
| Authors: | ID Bujtás, Csilla (Author)
ID Rote, Günter (Author)
ID Tuza, Zsolt (Author) |
|---|
| Files: |  PDF - Presentation file, download (468,61 KB)
MD5: 7D72CE182F954FDEED4ED7ACDE0307FF
 URL - Source URL, visit https://amc-journal.eu/index.php/amc/article/view/2771
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | fractional vertex cover, fractional transversal game, fractional domination game |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.01.2024 |
|---|
| Year of publishing: | 2024 |
|---|
| Number of pages: | 19 str. |
|---|
| Numbering: | Vol. 24, no. 3, article no. P3.05 |
|---|
| PID: | 20.500.12556/DiRROS-21312  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1855-3966 |
|---|
| DOI: | 10.26493/1855-3974.2771.4df |
|---|
| COBISS.SI-ID: | 202315011 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 24.01.2025 |
|---|
| Views: | 648 |
|---|
| Downloads: | 327 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
