Dear all, next Monday's Lecture and Colloquium will take place online via Zoom on December 6. Please find link to Zoom here: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password is required. You all are cordially invited! Location:
Time: Monday, December 6 - 14:15 h Title: Spanners and connectivity problems in temporal graphs Abstract:A graph whose edges only appear at certain points in time is called a temporal graph. Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this talk, I will focus on the concept of a temporal spanner, which is a subgraph of the input temporal graph that preserves temporal connectivity using as few edges (or labels) as possible. In stark contrast with standard graphs, it turns out that linear size spanners, and in fact, even sparse spanners (i.e., spanners with o(n^{^2}) edges) do not always exist in temporal graphs. After presenting basic notions and reviewing these astonishing negative results, I will present some good news as well; namely, sparse spanners always exist in *some* natural classes of temporal graphs. These include the cases when the underlying graph is complete (this talk) or when the labels are chosen at random (subsequent talk). If time permit, I will present two open questions, and discuss some recent attempts at solving them. Break Monday's Colloquium: Malte Renken (Technische
Universität Berlin) Time: Monday, December 6 - 16:00 h s.t. Title: Connectivity Thresholds in Random Temporal Graphs Abstract: You all are cordially invited! |