7 citations · 20 across the 11 of their papers we have counts for
19 papers
Disentangling the Computational Complexity of Network Untangling
Vincent Froese, Pascal Kunz, Philipp Zschoche
We study the network untangling problem introduced by Rozenshtein, Tatti, and Gionis [DMKD 2021], which is a variant of Vertex Cover on temporal graphs -- graphs whose edge set cha…
Restless Temporal Path Parameterized Above Lower Bounds
Philipp Zschoche
Reachability questions are one of the most fundamental algorithmic primitives in temporal graphs -- graphs whose edge set changes over discrete time steps. A core problem here is t…
Interference-free Walks in Time: Temporally Disjoint Paths
Nina Klobas, George B. Mertzios, Hendrik Molter +2
We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal pa…
Optimal Virtual Network Embeddings for Tree Topologies
Aleksander Figiel, Leon Kellerhals, Rolf Niedermeier +3
The performance of distributed and data-centric applications often critically depends on the interconnecting network. Applications are hence modeled as virtual networks, also accou…
Parameterized Algorithms for Diverse Multistage Problems
Leon Kellerhals, Malte Renken, Philipp Zschoche
The world is rarely static -- many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the "multistage" view on computatio…
Temporal Reachability Minimization: Delaying vs. Deleting
Hendrik Molter, Malte Renken, Philipp Zschoche
We study spreading processes in temporal graphs, i. e., graphs whose connections change over time. These processes naturally model real-world phenomena such as infectious diseases…
The Complexity of Transitively Orienting Temporal Graphs
George B. Mertzios, Hendrik Molter, Malte Renken +2
In a temporal network with discrete time-labels on its edges, entities and information can only ``flow'' along sequences of edges whose time-labels are non-decreasing (resp. increa…
A Faster Parameterized Algorithm for Temporal Matching
Philipp Zschoche
A temporal graph is a sequence of graphs (called layers) over the same vertex set -- describing a graph topology which is subject to discrete changes over time. A -temporal matc…
Using a geometric lens to find k disjoint shortest paths
Matthias Bentert, André Nichterlein, Malte Renken +1
Given an undirected -vertex graph and pairs of terminal vertices , the -Disjoint Shortest Paths (-DSP)-problem asks whether there are …
As Time Goes By: Reflections on Treewidth for Temporal Graphs
Till Fluschnik, Hendrik Molter, Rolf Niedermeier +2
Treewidth is arguably the most important structural graph parameter leading to algorithmically beneficial graph decompositions. Triggered by a strongly growing interest in temporal…
Multistage s-t Path: Confronting Similarity with Dissimilarity
Till Fluschnik, Rolf Niedermeier, Carsten Schubert +1
Addressing a quest by Gupta et al. [ICALP'14], we provide a first, comprehensive study of finding a short s-t path in the multistage graph model, referred to as the Multistage s-t…
The Computational Complexity of Finding Temporal Paths under Waiting Time Constraints
Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter +1
Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, grap…
Multistage Vertex Cover
Till Fluschnik, Rolf Niedermeier, Valentin Rohm +1
Covering all edges of a graph by a small number of vertices, this is the NP-complete Vertex Cover problem. It is among the most fundamental graph-algorithmic problems. Following a…
Computing Maximum Matchings in Temporal Graphs
George B. Mertzios, Hendrik Molter, Rolf Niedermeier +2
Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph , a temporal graph is represented by assigning a set of integ…
Representative families for matroid intersections, with applications to location, packing, and covering problems
René van Bevern, Oxana Yu. Tsidulko, Philipp Zschoche
We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location p…
Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
Tomohiro Koana, Viatcheslav Korenwein, André Nichterlein +2
Finding a maximum-cardinality or maximum-weight matching in (edge-weighted) undirected graphs is among the most prominent problems of algorithmic graph theory. For -vertex and $…
Temporal Graph Classes: A View Through Temporal Separators
Till Fluschnik, Hendrik Molter, Rolf Niedermeier +2
We investigate the computational complexity of separating two distinct vertices s and z by vertex deletion in a temporal graph. In a temporal graph, the vertex set is fixed but the…
The Complexity of Finding Small Separators in Temporal Graphs
Philipp Zschoche, Till Fluschnik, Hendrik Molter +1
Temporal graphs are graphs with time-stamped edges. We study the problem of finding a small vertex set (the separator) with respect to two designated terminal vertices such that th…
On the Computational Complexity of Variants of Combinatorial Voter Control in Elections
Leon Kellerhals, Viatcheslav Korenwein, Philipp Zschoche +2
Voter control problems model situations in which an external agent tries toaffect the result of an election by adding or deleting the fewest number of voters. The goal of the agent…