28 citations · 71 across the 13 of their papers we have counts for
17 papers · 1 filter
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…
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…
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…
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…
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…
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…