7 citations · 9 across the 8 of their papers we have counts for
12 papers · 1 filter
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…
A Multistage View on 2-Satisfiability
Till Fluschnik
We study -SAT in the multistage model, focusing on the linear-time solvable 2-SAT. Herein, given a sequence of -CNF fomulas and a non-negative integer , the question is wh…
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…