On the Fixed Parameter Tractability of Minimum Temporal Connectivity
MetadataShow full item record
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.