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

        Minimum Feedback Vertex Set for graphs of restricted degree

        Thumbnail
        View/Open
        Minimum-FVS-IG-de-Wolff.pdf (391.9Kb)
        Publication date
        2017
        Author
        Wolff, I.G. de
        Metadata
        Show full item record
        Summary
        Finding a minimum feedback vertex set, a set whose removal makes a graph acyclic, is an NP-complete problem. We study the behaviour of existing algorithms for this problem on bounded degree graphs. Using the notion of generalized degree, we show that the algorithm of Fomin et al. [2] runs in time O∗ (1.6181n) on graphs of maximum degree three (al- though this case is polynomial-time solvable using a different algorithm) and in contrast, show that for graphs of degree four the generalized de- gree can become arbitrarily large. We show that the algorithm of Xiao [7] runs in time O∗ (1.7180n) on degree four graphs, which improves the best known bound for this case. Finally, we show that we cannot extend the measure of Fomin et al. [2] by using the generalized degree.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/26953
        Collections
        • Theses
        Utrecht university logo