43 citations · 89 across the 32 of their papers we have counts for
6 papers · 1 filter
Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring
Till Fluschnik, Pascal Kunz
We consider the algorithmic complexity of recognizing bipartite temporal graphs. Rather than defining these graphs solely by their underlying graph or individual layers, we define…
Polynomial Turing Kernels for Clique with an Optimal Number of Queries
Till Fluschnik, Klaus Heeger, Danny Hermelin
A polynomial Turing kernel for some parameterized problem is a polynomial-time algorithm that solves using queries to an oracle of whose sizes are upper-bounded by some…
Most Classic Problems Remain NP-hard on Relative Neighborhood Graphs and their Relatives
Pascal Kunz, Till Fluschnik, Rolf Niedermeier +1
Proximity graphs have been studied for several decades, motivated by applications in computational geometry, geography, data mining, and many other fields. However, the computation…
3-Coloring on Regular, Planar, and Ordered Hamiltonian Graphs
Dario Cavallaro, Till Fluschnik
We prove that 3-Coloring remains NP-hard on 4- and 5-regular planar Hamiltonian graphs, strengthening the results of Dailey [Disc. Math.'80] and Fleischner and Sabidussi [J. Graph.…
Feedback Vertex Set on Hamiltonian Graphs
Dario Cavallaro, Till Fluschnik
We study the computational complexity of Feedback Vertex Set on subclasses of Hamiltonian graphs. In particular, we consider Hamiltonian graphs that are regular or are planar and r…
Placing Green Bridges Optimally, with a Multivariate Analysis
Till Fluschnik, Leon Kellerhals
We study the problem of placing wildlife crossings, such as green bridges, over human-made obstacles to challenge habitat fragmentation. The main task herein is, given a graph desc…