View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        MM-Width: Observations, Algorithms and Approximations

        Thumbnail
        View/Open
        thesis.pdf (1.470Mb)
        Publication date
        2017
        Author
        Brouwer, S.F.A.M.
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/27807
        Collections
        • Theses
        Utrecht university logo