tr-announce

Download

tr-announce@lists.rwth-aachen.de

December 2010

1 participants
2 discussions

2010-20: Degrees of Lookahead in Context-free Infinite Games
by Carsten Fuhs 29 Dec '10

29 Dec '10

The following technical report is available from http://aib.informatik.rwth-aachen.de: Degrees of Lookahead in Context-free Infinite Games Wladimir Fridman, Christof Löding, Martin Zimmermann AIB 2010-20 We continue the investigation of delay games, infinite games in which one player may postpone her moves for some time to obtain a lookahead on her opponents moves. We show that the problem of determining the winner of such a game is undecidable for context-free winning conditions. Furthermore, we show that the necessary lookahead to win a context-free delay game cannot be bounded by an elementary function.

1 0

2010-19: Experimental Evaluation of an Independent Set Algorithm
by Carsten Fuhs 23 Dec '10

23 Dec '10

The following technical report is available from http://aib.informatik.rwth-aachen.de: Experimental Evaluation of an Independent Set Algorithm Felix Reidl AIB 2010-19 Following up the development of the currently fastest Independent Set algorithm (Kneis, Langer, Rossmanith, 2009) we present a practical evaluation, both on real-world data taken from common biological problems and on synthetic data. In order to get a clearer picture we measure different aspects of our implementation, especially the different polynomial-time reduction rules. The main purpose of this report is to show that algorithms with provable upper bounds can indeed be used to solve practical instances, though some care must be taken in the transfer of algorithm to code.

1 0