Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646954 | Discrete Mathematics | 2015 | 7 Pages |
Abstract
We consider the weighted version of the Tron game on graphs where two players, Alice and Bob, each build their own path by claiming one vertex at a time, starting with Alice. The vertices carry non-negative weights that sum up to 1 and either player tries to claim a path with larger total weight than the opponent. We show that if the graph is a tree then Alice can always ensure she receives 1/5 less than Bob or better, and this is best possible.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daniel Hoske, Jonathan Rollin, Torsten Ueckerdt, Stefan Walzer,