Games on interval and permutation graph representations

Jessica Enright, Lorna Stewart

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Pages (from-to)87-103
Number of pages17
JournalTheoretical Computer Science
Volume609
DOIs
Publication statusPublished - Jan 2016

Fingerprint

Dive into the research topics of 'Games on interval and permutation graph representations'. Together they form a unique fingerprint.

Cite this