tr-announce Dezember 2010

tr-announce@lists.rwth-aachen.de

1 Teilnehmer
2 Diskussionen

2010-20: Degrees of Lookahead in Context-free Infinite Games

von Carsten Fuhs

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.

13 Jahre, 3 Monate

2010-19: Experimental Evaluation of an Independent Set Algorithm

von Carsten Fuhs

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.

13 Jahre, 3 Monate

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

tr-announce Dezember 2010