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

        Variations on Boolean-width

        Thumbnail
        View/Open
        thesis.pdf (1.503Mb)
        Publication date
        2015
        Author
        Brinke, C.B. ten
        Metadata
        Show full item record
        Summary
        This thesis is about the graph parameter boolean-width and several related parameters. In particular we investigate the restriction of boolean-width to linear decompositions, called linear boolean-width. Improving upon existing work, we give several new algorithms, both exact and heuristical, and test these experimentally. We also look at reduction rules for linear boolean-width. After that we consider cost variants of these parameters, which optimize a decomposition by means of minimizing the sum of all cut values in a decomposition rather than taking the maximum. We give a general non-trivial exact algorithm to compute decompositions with minimal f-cost, for any cut function f. Finally we evaluate these topics and give suggestions about what is worth further investigating.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/22878
        Collections
        • Theses
        Utrecht university logo