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

        The Algorithmic Complexity of Tree-Clique Width

        Thumbnail
        View/Open
        Master_thesis-Chris Aronis-final version 2.pdf (518.2Kb)
        Publication date
        2021
        Author
        Aronis, Chris
        Metadata
        Show full item record
        Summary
        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. Therefore, we introduce tree-clique width, denoted by tcl(G) for a graph G, a new width measure for tree decompositions. The main aim of such a parameter is to extend the algorithmic gains of tree-width on more structured and dense graphs. In this paper, we show that tree-clique width is NP-complete and that there is no constant factor approximation algorithm for any constant value c. We also provide algorithms to compute tree-clique width for general graphs and for special graphs such as cographs and permutation graphs. We seek to understand further tree-clique width and its properties and to research whether it can be used as an alternative where tree-width fails.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/204
        Collections
        • Theses
        Utrecht university logo