Approximability of Minimum Temporally Connected Subgraphs
Anne-Sophie Himmel (TU Berlin)
Many modern systems are highly dynamic and relations between
objects vary over time. One model to capture these dynamics are
temporal graphs - graphs that change over time. In this talk, we
consider temporal graphs with discrete time labels and investigate
the approximability of minimum temporally connected spanning
More precise, we consider the problem of computing a minimum weight subset of temporal edges that preserve the connectivity of a given temporal graph from a given vertex r (r-MTC). We show that the approximability of r-MTC is closely related to the approximability of Directed Steiner Tree. Furthermore, we show that r-MTC can be solved in polynomial time if the underlying graph has bounded treewidth.
Back to the research colloquium site.