8 papers
Freeze-Tag with Return
Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse +3
In the standard Freeze-Tag Problem (FTP), an initially awake robot (the source) is in charge of waking up a swarm of sleeping robots by moving towards them, given that all the awak…
Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics
Justine Cauvi, Nils Morawietz, Laurent Viennot
In this work, we follow the current trend on temporal graph realization, where one is given a property P and the goal is to determine whether there is a temporal graph, that is, a…
Temporal Graph Realization With Bounded Stretch
George B. Mertzios, Hendrik Molter, Nils Morawietz +1
A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first time steps, and then it reappears recurrently every time s…
Realization of Temporally Connected Graphs Based on Degree Sequences
Arnaud Casteigts, Michelle Döring, Nils Morawietz
Given an undirected graph , the problem of deciding whether admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al.,…
Recognizing and Realizing Temporal Reachability Graphs
Thomas Erlebach, Othon Michail, Nils Morawietz
A temporal graph can be represented by an underlying graph together with a function that assigns to each edge the set of time steps durin…
Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
Kaja Balzereit, Niels Grüttemeier, Nils Morawietz +3
In this work, we study the task of scheduling jobs on a single machine with sequence dependent family setup times under the goal of minimizing the makespan, that is, the completion…
Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
Arnaud Casteigts, Nils Morawietz, Petra Wolf
A temporal graph is a graph whose edges only appear at certain points in time. Reachability in these graphs is defined in terms of paths that traverse the edges in chronological or…
A Timecop's Chase Around the Table
Nils Morawietz, Petra Wolf
We consider the cops and robber game variant consisting of one cop and one robber on time-varying graphs (TVG). The considered TVGs are edge periodic graphs, i.e., for each edge, a…