
Most Classic Problems Remain NPhard on Relative Neighborhood Graphs and their Relatives
Proximity graphs have been studied for several decades, motivated by app...
read it

3Coloring on Regular, Planar, and Ordered Hamiltonian Graphs
We prove that 3Coloring remains NPhard on 4 and 5regular planar Hami...
read it

Feedback Vertex Set on Hamiltonian Graphs
We study the computational complexity of Feedback Vertex Set on subclass...
read it

Placing Green Bridges Optimally, with a Multivariate Analysis
We study the problem of placing wildlife crossings, such as green bridge...
read it

A Multistage View on 2Satisfiability
We study qSAT in the multistage model, focusing on the lineartime solv...
read it

Multistage Committee Election
Electing a single committee of a small size is a classical and wellunde...
read it

As Time Goes By: Reflections on Treewidth for Temporal Graphs
Treewidth is arguably the most important structural graph parameter lead...
read it

Multistage st Path: Confronting Similarity with Dissimilarity
Addressing a quest by Gupta et al. [ICALP'14], we provide a first, compr...
read it

Multistage Vertex Cover
Covering all edges of a graph by a minimum number of vertices, this is t...
read it

On (1+ε)approximate problem kernels for the Rural Postman Problem
Given a graph G=(V,E) with edge weights ω E→ N∪{0} and a subset R⊆ E of ...
read it

On the Computational Complexity of Length and NeighborhoodConstrained Path Problems
Finding paths in graphs is a fundamental graphtheoretic task. In this w...
read it

Parameterized algorithms and data reduction for the short secluded stpath problem
Given a graph G=(V,E), two vertices s,t∈ V, and two integers k,ℓ, we sea...
read it

Parameterized algorithms and data reduction for safe convoy routing
We study a problem that models safely routing a convoy through a transpo...
read it

A More FineGrained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
We study the NPhard Shortest Path Most Vital Edges problem arising in t...
read it

Temporal Graph Classes: A View Through Temporal Separators
We investigate the computational complexity of separating two distinct v...
read it

Fair Knapsack
We study the following multiagent variant of the knapsack problem. We ar...
read it

On Efficiently Finding Small Separators in Temporal Graphs
Vertex separators, that is, vertex sets whose deletion disconnects two d...
read it

The Computational Complexity of Finding Separators in Temporal Graphs
Vertex separators, that is, vertex sets whose deletion disconnects two d...
read it

Kernelization Lower Bounds for Finding Constant Size Subgraphs
Kernelization is an important tool in parameterized algorithmics. The go...
read it
Till Fluschnik
is this you? claim profile