direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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 subgraphs.
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.


Anne-Sophie Himmel
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras