Name
Abstract | ||
|---|---|---|
We describe combinatorial games on graphs in which two players antagonistically build a representation of a subgraph of a given graph. We show that for a large class of these games, determining whether a given instance is a winning position for the next player is PSPACE-hard. In contrast, we give polynomial time algorithms for solving some versions of the games on trees. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2015.09.009 | Theoretical Computer Science |
Keywords | Field | DocType |
Games on graphs,Permutation graphs,Interval graphs,Combinatorial games,Set representations of graphs | Permutation graph,Discrete mathematics,Block graph,Combinatorial game theory,Combinatorics,Forbidden graph characterization,Interval graph,Pathwidth,Universal graph,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
609 | P1 | 0304-3975 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jessica Enright | 1 | 8 | 3.89 |
| Lorna Stewart | 2 | 361 | 28.05 |