13 papers
Reconfiguration of Temporal Networks under Reachability Constraints
Othon Michail, George Skretas, Georg Tennigkeit +1
Temporal networks model dynamic systems in which edges represent interactions and labels specify when these interactions occur. Examples include transportation networks, time-sensi…
Distributed Symmetry Breaking on Hyperbolic Random Graphs
Yannic Maus, Janosch Ruff, Sonia Simons +1
Real-world networks like the internet share patterns like a power law degree distribution and a high clustering coefficient. Many of these properties are captured by the generative…
Maximizing Reachability via Shifting of Temporal Paths
Argyrios Deligkas, Michelle Döring, Eduard Eiben +2
We examine the problem of maximizing the reachability of a given source in temporal graphs that are given as the union of k temporal paths, i.e., every given path is a sequence of…
Temporal Graph Reconfiguration for Always-Connected Graphs
Paul Sievers, George Skretas, Georg Tennigkeit
Network redesign problems ask for modifications to the edges of a given graph to satisfy certain properties. In temporal graphs, where edges are only active at certain times, we ar…
Temporal Routing in Static Networks: The Schedule Completion Problem
Michelle Döring, Michelle Döring, Niklas Mohrin +1
We introduce the Temporally Edge Disjoint Schedule Completion (TEDSC) problem in which we need to cover a set of temporal edge demands by routing temporal walks through a d…
Temporal Network Creation Games: The Impact of Flexible Labels
Hans Gawendowicz, Nicolas Klodt, Aleksandrs Morgensterns +1
A crucial aspect of research is understanding how real-world networks, such as transportation and information networks, are formed. A prominent model for such networks was introduc…