| dc.rights.license | CC-BY-NC-ND | |
| dc.contributor.advisor | Bodlaender, Hans | |
| dc.contributor.author | Nouwt, Florian | |
| dc.date.accessioned | 2022-05-17T00:00:35Z | |
| dc.date.available | 2022-05-17T00:00:35Z | |
| dc.date.issued | 2022 | |
| dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/41566 | |
| dc.description.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. | |
| dc.description.sponsorship | Utrecht University | |
| dc.language.iso | EN | |
| dc.subject | 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 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. | |
| dc.title | A simulated annealing method for computing rank-width | |
| dc.type.content | Master Thesis | |
| dc.rights.accessrights | Open Access | |
| dc.subject.keywords | rank-width; f4-rank-width; GF(4)-rank-width; maximum matching-width; simulated annealing; local search; graph; width parameter; branch-decomposition; rank-decomposition | |
| dc.subject.courseuu | Computing Science | |
| dc.thesis.id | 3906 | |
