7 papers
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…
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…
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…
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, …
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…