A simulated annealing method for computing rank-width
Summary
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.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Morphodynamic equilibrium of width and bed level profile of an estuary in response to adjustable channel widths
Janssen, Michal (2022)In this thesis, the morphodynamic equilibrium of the width and bed level profile of estuaries is studied. This is done by using an one-dimensional hydrodynamic and morphodynamic model that includes variable channel widths. ... -
The Algorithmic Complexity of Tree-Clique Width
Aronis, Chris (2021)Tree-width has been proven to be a useful parameter to design fast and efficient algorithms for intractable problems. However, while tree-width is low on relatively sparse graphs can be arbitrary high on dense graphs. ... -
Experimental Research and Algorithmic Improvements involving the Graph Parameter Boolean-width
Houten, F.J.P. van (2015)In this thesis, we investigate numerous algorithms that make use of boolean decompositions. We provide a new algorithm for computing the representatives of linear decompositions. These representatives are the indices for ...