dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Bodlaender, H.L. | |
dc.contributor.advisor | Rooij, J.M.M. van | |
dc.contributor.author | Brouwer, S.F.A.M. | |
dc.date.accessioned | 2017-09-28T17:01:32Z | |
dc.date.available | 2017-09-28T17:01:32Z | |
dc.date.issued | 2017 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/27807 | |
dc.description.abstract | In this thesis we investigate maximum matching-width (MM-width) further. MM-width is a graph width parameter similar to treewidth, related to the number of maximum matchings made in an induced bipartite graph made from partitions over the vertices of a graph. We improve the link between the value of maximum matching-width and the value of treewidth of a graph G to mmw(G) <= tw(G). We also give a bounded dynamic programming algorithm BMMDP to calculate the MM-width of a graph exactly. In addition to the exact algorithm we look into approximating the MM-width of graphs from above by using optimization algorithms based on local search and evolutionary algorithms.
In the thesis we also make general observations about maximum matching-width, investigate the MM-width of standard graphs and come up with a set of safe kernelization rules to improve the performance of our algorithms. We also use the link between maximum matching-width and the other width parameters, the MM-widths of standard graphs and widths found during run time to add upper and lower bounds to the exact algorithm. | |
dc.description.sponsorship | Utrecht University | |
dc.format.extent | 1541934 | |
dc.format.mimetype | application/pdf | |
dc.language.iso | en_US | |
dc.title | MM-Width: Observations, Algorithms and Approximations | |
dc.type.content | Master Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | maximum matching-width; graph decomposition; width parameter; graph algorithm; treewidth; approximation | |
dc.subject.courseuu | Computing Science | |