On the Fixed Parameter Tractability of Minimum Temporal Connectivity

dc.rights.license	CC-BY-NC-ND
dc.contributor.advisor	Bodlaender, Hans
dc.contributor.author	Heuseveldt, Jens
dc.date.accessioned	2022-12-07T01:01:14Z
dc.date.available	2022-12-07T01:01:14Z
dc.date.issued	2022
dc.identifier.uri	https://studenttheses.uu.nl/handle/20.500.12932/43287
dc.description.abstract	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.
dc.description.sponsorship	Utrecht University
dc.language.iso	EN
dc.subject	Minimum Temporal Connectivity is fixed parameter tractable with treewidth and lifetime as combined parameter. The algorithm provided uses dynamic programming on a nice tree decomposition.
dc.title	On the Fixed Parameter Tractability of Minimum Temporal Connectivity
dc.type.content	Master Thesis
dc.rights.accessrights	Open Access
dc.subject.keywords	Temporal graphs;treewidth;FPT;fixed parameter tractability;minimum temporal connectivity;activation propagation;nice tree decomposition
dc.subject.courseuu	Computing Science
dc.thesis.id	12462