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

        On the Fixed Parameter Tractability of Minimum Temporal Connectivity

        Thumbnail
        View/Open
        Temporal_Graph_Thesis_v4.pdf (415.8Kb)
        Publication date
        2022
        Author
        Heuseveldt, Jens
        Metadata
        Show full item record
        Summary
        Temporal graphs allow encoding time-dependent information in graphs. However, problems on temporal graphs tend to be more complex than their counterparts on static graphs. The Minimum Temporal Connectivity and Maximum Temporal Matching problems are both NP-hard. In this thesis we provide an algorithm that proves that the Minimum Temporal Connectivity problem is fixed parameter tractable, using the graph lifetime and treewidth as combined parameter.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/43287
        Collections
        • Theses
        Utrecht university logo