--- res: bibo_abstract: - Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP ∩ co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth. @eng bibo_authorlist: - foaf_Person: foaf_givenName: Andrey foaf_name: Grinshpun, Andrey foaf_surname: Grinshpun - foaf_Person: foaf_givenName: Pakawat foaf_name: Phalitnonkiat, Pakawat foaf_surname: Phalitnonkiat - foaf_Person: foaf_givenName: Sasha foaf_name: Rubin, Sasha foaf_surname: Rubin foaf_workInfoHomepage: http://www.librecat.org/personId=2EC51194-F248-11E8-B48F-1D18A9856A87 - foaf_Person: foaf_givenName: Andrei foaf_name: Tarfulea, Andrei foaf_surname: Tarfulea bibo_doi: 10.1016/j.tcs.2013.11.032 bibo_volume: 521 dct_date: 2014^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/03043975 dct_language: eng dct_publisher: Elsevier@ dct_title: Alternating traps in Muller and parity games@ ...