28 citations · 71 across the 13 of their papers we have counts for
3 papers · 1 filter
On the Parameterized Complexity of Computing Balanced Partitions in Graphs
René van Bevern, Andreas Emil Feldmann, Manuel Sorge +1
A balanced partition is a clustering of a graph into a given number of equal-sized parts. For instance, the Bisection problem asks to remove at most k edges in order to partition t…
Tree Deletion Set has a Polynomial Kernel (but no OPT^O(1) approximation)
Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh +1
In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G-S i…
On Structural Parameterizations for the 2-Club Problem
Sepp Hartung, Christian Komusiewicz, André Nichterlein +1
The NP-hard 2-Club problem is, given an undirected graph G=(V,E) and l\in N, to decide whether there is a vertex set S\subseteq V of size at least l such that the induced subgraph…