43 citations · 89 across the 32 of their papers we have counts for
5 papers · 1 filter
On approximate data reduction for the Rural Postman Problem: Theory and experiments
René van Bevern, Till Fluschnik, Oxana Yu. Tsidulko
Given an undirected graph with edge weights and a subset of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of…
On the Computational Complexity of Length- and Neighborhood-Constrained Path Problems
Max-Jonathan Luckow, Till Fluschnik
Finding paths in graphs is a fundamental graph-theoretic task. In this work, we we are concerned with finding a path with some constraints on its length and the number of vertices…
Parameterized algorithms and data reduction for the short secluded --path problem
René van Bevern, Till Fluschnik, Oxana Yu. Tsidulko
Given a graph , two vertices , and two integers , the Short Secluded Path problem is to find a simple --path with at most vertices and n…
A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
Cristina Bazgan, Till Fluschnik, André Nichterlein +2
We study the NP-hard Shortest Path Most Vital Edges problem arising in the context of analyzing network robustness. For an undirected graph with positive integer edge lengths and t…
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…