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

        Spanheight, A Natural Extension of Bandwidth and Treedepth

        Thumbnail
        View/Open
        roden.pdf (741.9Kb)
        Publication date
        2015
        Author
        Roden, N. van
        Metadata
        Show full item record
        Summary
        In graph theory, the treedepth problem finds depth first search spanning trees of bounded height and is NP-Complete. We study an extension of treedepth where we bound the distance between adjacent vertices in the depth first search spanning tree. This graph problem has a close resemblance to bandwidth and treespan. We call this problem spanheight and show that its NP-Complete. We introduce a single exponential algorithm using O(n^2 9^n) time and O(n^2 2^n) space. We look at meta-theorems for proving membership in FPT, and present an O(n t^4 2^(7t^3 2^t log(t)) ) time and O(n 2^(3t^3 2^t log(t))) space FPT algorithm by parameterizing with treedepth.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/28433
        Collections
        • Theses
        Utrecht university logo