1 citations · 1 across the 11 of their papers we have counts for
13 papers
Temporal Routing in Static Networks: The Schedule Completion Problem
Michelle Döring, Niklas Mohrin, George Skretas
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…
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 ,…
The River Method
Michelle Döring, Markus Brill, Jobst Heitzig
We introduce River, a novel Condorcet-consistent voting method that is based on pairwise majority margins and can be seen as a simplified variation of Tideman's Ranked Pairs method…
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.,…
Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs
Michelle Döring
We present the first comprehensive analysis of temporal settings for directed temporal graphs, fully resolving their hierarchy with respect to support, reachability, and induced-re…
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…
Catch Me If You Can: Finding the Source of Infections in Temporal Networks
Ben Bals, Michelle Döring, Nicolas Klodt +1
Source detection (SD) is the task of finding the origin of a spreading process in a network. Algorithms for SD help us combat diseases, misinformation, pollution, and more, and hav…
How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs
Argyrios Deligkas, Michelle Döring, Eduard Eiben +3
Logistics and transportation networks require a large amount of resources to realize necessary connections between locations and minimizing these resources is a vital aspect of pla…
Margin of Victory for Weighted Tournament Solutions
Michelle Döring, Jannik Peters
Determining how close a winner of an election is to becoming a loser, or distinguishing between different possible winners of an election, are major problems in computational socia…
Schelling Games with Continuous Types
Davide Bilò, Vittorio Bilò, Michelle Döring +3
In most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socioeconomic lines. This phenomenon is widely known as residential segregation and h…
Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source
Argyrios Deligkas, Michelle Döring, Eduard Eiben +2
We consider the influence maximization problem over a temporal graph, where there is a single fixed source. We deviate from the standard model of influence maximization, where the…