A simulated annealing method for computing rank-width

Abstract

In this thesis we show that simulated annealing is a very viable heuristic method for approximating rank-width and other branch-decomposition based width parameters. We present the various aspects of the algorithm in detail and discuss the design choices that were made with the help of practical experiments. Finally, extensive benchmarks were performed to assess the performance of the algorithm. We improved many of the currently best known rank-width upper bounds and show the first practical results for F4-rank-width and maximum matching-width.