AIB 2010-19: Experimental Evaluation of an Independent Set Algorithm

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.