5 papers · 1 filter
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.,…
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…