28 citations · 71 across the 13 of their papers we have counts for
24 papers
Parameterizing Cluster Editing by the Number of Deletions
Vincent Froese, Leon Kellerhals, Frank Sommer +2
In Cluster Editing, we are given a graph and an integer and ask whether at most edge insertions and deletions turn into a disjoint union of cliques. Komusiewicz and…
On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations
Václav Blažej, Pratibha Choudhary, Dušan Knop +3
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important a…
Polynomial Kernels for Tracking Shortest Paths
Václav Blažej, Pratibha Choudhary, Dušan Knop +3
Given an undirected graph , vertices , and an integer , Tracking Shortest Paths requires deciding whether there exists a set of vertices su…
Hedonic Diversity Games: A Complexity Picture with More than Two Colors
Robert Ganian, Thekla Hamm, Dušan Knop +2
Hedonic diversity games are a variant of the classical Hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly target…
Generating faster algorithms for d-Path Vertex Cover
Radovan Červený, Ondřej Suchý
Many algorithms which exactly solve hard problems require branching on more or less complex structures in order to do their job. Those who design such algorithms often find themsel…
Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Václav Blažej, Pratibha Choudhary, Dušan Knop +3
Consider a vertex-weighted graph with a source and a target . Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of track…
On Kernels for d-Path Vertex Cover
Radovan Červený, Pratibha Choudhary, Ondřej Suchý
In this paper we study the kernelization of the -Path Vertex Cover (-PVC) problem. Given a graph , the problem requires finding whether there exists a set of at most v…
Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
Martin Kučera, Ondřej Suchý
The Minimum Eccentricity Shortest Path Problem consists in finding a shortest path with minimum eccentricity in a given undirected graph. The problem is known to be NP-complete and…
Waypoint Routing on Bounded Treewidth Graphs
Šimon Schierreich, Ondřej Suchý
In the \textsc{Waypoint Routing Problem} one is given an undirected capacitated and weighted graph , a source-destination pair and a set , of \emp…
Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem
Josef Malík, Ondřej Suchý, Tomáš Valla
We consider the subgraph isomorphism problem where, given two graphs G (source graph) and F (pattern graph), one is to decide whether there is a (not necessarily induced) subgraph…
Faster FPT Algorithm for 5-Path Vertex Cover
Radovan Červený, Ondřej Suchý
The problem of -Path Vertex Cover, -PVC lies in determining a subset of vertices of a given graph such that does not contain a path on verti…
A Parameterized Complexity View on Collapsing k-Cores
Junjie Luo, Hendrik Molter, Ondrej Suchy
We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining…
Complexity of the Steiner Network Problem with Respect to the Number of Terminals
Eduard Eiben, Dušan Knop, Fahad Panolan +1
In the Directed Steiner Network problem we are given an arc-weighted digraph , a set of terminals , and an (unweighted) directed request graph with $V(R)=T…
Cluster Editing for Multi-Layer and Temporal Graphs
Jiehua Chen, Hendrik Molter, Manuel Sorge +1
Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-L…
Fixed-Parameter Algorithms for DAG Partitioning
René van Bevern, Robert Bredereck, Morgan Chopin +4
Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM SIGKDD 2009] as DAG Partitioning: given an arc-weighted directed acyclic…
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
René van Bevern, Till Fluschnik, George B. Mertzios +3
This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum s-t separators, feed…
A Simple Streaming Bit-parallel Algorithm for Swap Pattern Matching
Václav Blažej, Ondřej Suchý, Tomáš Valla
The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols. The goal is to design fast matching a…
On Directed Steiner Trees with Multiple Roots
Ondřej Suchý
We introduce a new Steiner-type problem for directed graphs named \textsc{-Root Steiner Tree}. Here one is given a directed graph and two subsets of its vertices, …
A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
René van Bevern, Rolf Niedermeier, Ondřej Suchý
We study the problem of non-preemptively scheduling jobs, each job with a release time , a deadline , and a processing time , on parallel identical machi…
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…
Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan +2
We study the parameterized complexity of the directed variant of the classical {\sc Steiner Tree} problem on various classes of directed sparse graphs. While the parameterized comp…
Beyond Max-Cut: λ-Extendible Properties Parameterized Above the Poljak-Turzík Bound
Matthias Mnich, Geevarghese Philip, Saket Saurabh +1
Poljak and Turzík (Discrete Math. 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any…