9 papers
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…
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.…
FO and MSO Model Checking on Temporal Graphs
Michelle Döring, Jessica Enright, Laura Larios-Jones +1
Algorithmic meta-theorems provide an important tool for showing tractability of graph problems on graph classes defined by structural restrictions. While such results are well esta…
Cost-Free Neutrality for the River Method
Michelle Döring, Jannes Malanowski, Stefan Neubert
Recently, the River Method was introduced as novel refinement of the Split Cycle voting rule. The decision-making process of River is closely related to the well established Ranked…
Parameterized Complexity of Vehicle Routing
Michelle Döring, Jan Fehse, Tobias Friedrich +6
The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph ,…
Dynamic Network Discovery via Infection Tracing
Ben Bals, Michelle Döring, Nicolas Klodt +1
Researchers, policy makers, and engineers need to make sense of data from spreading processes as diverse as rumor spreading in social networks, viral infections, and water contamin…