4 Result(s)
within
Ondřej Suchý
Algorithm Analysis and Problem Complexity
Algorithms
Data Structures
-
Chapter and Conference Paper
On Directed Steiner Trees with Multiple Roots
We introduce a new Steiner-type problem for directed graphs named q-Root Steiner Tree. Here one is given a directed graph \(G=(V,A)\) ...
-
Chapter and Conference Paper
On the Parameterized Complexity of Computing Graph Bisections
The Bisection problem asks for a partition of the vertices of a graph into two equally sized sets, while minimizing the cut size. This is the number of edges connecting the two vertex sets. Bisection has been tho...
-
Chapter and Conference Paper
Parameterized Complexity of Generalized Domination Problems
Given two sets σ, ρ of nonnegative integers, a set S of vertices of a graph G is (σ,ρ)-dominating if |S ∩ N(v)| ∈ σ for every vertex v ∈ S, and |S ∩ N(v)| ∈ ρ for every v ∉ S. This concept, introduced by Telle in...
-
Chapter and Conference Paper
Parameterized Complexity of Arc-Weighted Directed Steiner Problems
We initiate a systematic parameterized complexity study of three fundamental network design problems on arc-weighted directed graphs: Directed Steiner Tree, Strongly Connected Steiner Subgraph, and Directed Stein...
