Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-121 | 22nd September 2014 09:28

Graph Structure and Parity Games

RSS-Feed




TR14-121
Authors: Sebastian Mueller
Publication: 28th September 2014 07:51
Downloads: 597
Keywords: 


Abstract:

We investigate the possible structural changes one can perform on a game graph without destroying the winning regions of the players playing a parity game on it. More precisely, given a game graph $(G,p)$ for which we can efficiently compute winning regions, can we remove or add a vertex or edge or change a single priority and maintain at least part of the winning region? Also, what about restricted classes of graphs, such as planar, $k$-connected and the like?



ISSN 1433-8092 | Imprint