Independent Set on P5-free graphs, an empirical study
Master thesis
Permanent lenke
https://hdl.handle.net/1956/10946Utgivelsesdato
2015-11-20Metadata
Vis full innførselSamlinger
Sammendrag
We implement the recent polynomial time algorithm for the independent set problem on P5-free graphs, and study the performance of this algorithm on graphs of size up to 50. Our empirical results show that the algorithm is probably much faster than its theoretical running-time upperbound.