1 citations · 3 across the 8 of their papers we have counts for
11 papers
Parameterized Complexity of Temporal Agony
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann +1
Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarch…
Efficient parameterized approximation
Stefan Kratsch, Pascal Kunz
Many problems are NP-hard and, unless P = NP, do not admit polynomial-time exact algorithms. The fastest known exact algorithms exactly usually take time exponential in the input s…
Approximate Turing kernelization and lower bounds for domination problems
Stefan Kratsch, Pascal Kunz
An -approximate polynomial Turing kernelization is a polynomial-time algorithm that computes an -approximate solution for a parameterized optimization problem when given a…
On Computing Optimal Tree Ensembles
Christian Komusiewicz, Pascal Kunz, Frank Sommer +1
Random forests and, more generally, (decision\nobreakdash-)tree ensembles are widely used methods for classification and regression. Recent algorithmic advances allow to compute de…
Parameterized Algorithms for Colored Clustering
Leon Kellerhals, Tomohiro Koana, Pascal Kunz +1
In the Colored Clustering problem, one is asked to cluster edge-colored (hyper-)graphs whose colors represent interaction types. More specifically, the goal is to select as many ed…
In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks?
Pascal Kunz, Hendrik Molter, Meirav Zehavi
A temporal graph has an edge set that may change over discrete time steps, and a temporal path (or walk) must traverse edges that appear at increasing time steps. Accordingly, two…
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…
Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees
Leon Kellerhals, Tomohiro Koana, Pascal Kunz
Vertex Cover parameterized by the solution size k is the quintessential fixed-parameter tractable problem. FPT algorithms are most interesting when the parameter is small. Several…
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…
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…
Computational Complexity Aspects of Point Visibility Graphs
Anne-Sophie Himmel, Clemens Hoffmann, Pascal Kunz +2
A point visibility graph is a graph induced by a set of points in the plane where the vertices of the graph represent the points in the point set and two vertices are adjacent if a…