Graph sharing games: Complexity and connectivity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10141896" target="_blank" >RIV/00216208:11320/13:10141896 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.tcs.2012.12.029" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2012.12.029</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2012.12.029" target="_blank" >10.1016/j.tcs.2012.12.029</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Graph sharing games: Complexity and connectivity

Popis výsledku v původním jazyce

We study the following combinatorial game played by two players, Alice and Bob, which generalizes the pizza game considered by Brown, Winkler and others. Given a connected graph G with non-negative weights assigned to its vertices, the players alternately take one vertex of G in each turn. The first turn is Alice's. The vertices are to be taken according to one (or both) of the following two rules: (T) the subgraph of G induced by the taken vertices is connected during the whole game, (R) the subgraph of G induced by the remaining vertices is connected during the whole game. We show that if rules (T) and/or (R) are required then for every epsilon > 0 and for every k }= 1 there is a k-connected graph G for which Bob has a strategy to obtain (1 - epsilon) of the total weight of the vertices. This contrasts with the original pizza game played on a cycle, where Alice is known to have a strategy to obtain four-ninths of the total weight. We show that the problem of deciding whether Alice ha

Název v anglickém jazyce

Graph sharing games: Complexity and connectivity

Popis výsledku anglicky

We study the following combinatorial game played by two players, Alice and Bob, which generalizes the pizza game considered by Brown, Winkler and others. Given a connected graph G with non-negative weights assigned to its vertices, the players alternately take one vertex of G in each turn. The first turn is Alice's. The vertices are to be taken according to one (or both) of the following two rules: (T) the subgraph of G induced by the taken vertices is connected during the whole game, (R) the subgraph of G induced by the remaining vertices is connected during the whole game. We show that if rules (T) and/or (R) are required then for every epsilon > 0 and for every k }= 1 there is a k-connected graph G for which Bob has a strategy to obtain (1 - epsilon) of the total weight of the vertices. This contrasts with the original pizza game played on a cycle, where Alice is known to have a strategy to obtain four-ninths of the total weight. We show that the problem of deciding whether Alice ha

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

494

Číslo periodika v rámci svazku

July

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

14

Strana od-do

49-62

Kód UT WoS článku

000321422500006

EID výsledku v databázi Scopus

—