Graph sharing games: Complexity and connectivity

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Graph sharing games: Complexity and connectivity
Original language description
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
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Similar results(10)