10 Result(s)
within
Ondřej Suchý
Algorithm Analysis and Problem Complexity
Computer Graphics
Data Structures
-
Chapter and Conference Paper
Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
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 W[2]-hard with respect to the d...
-
Chapter and Conference Paper
Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem
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 of G isomorphic to F. While man...
-
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
Effective and Efficient Data Reduction for the Subset Interconnection Design Problem
The NP-hard Subset Interconnection Design problem is motivated by applications in designing vacuum systems and scalable overlay networks. It has as input a set V and a collection of subsets V 1, V
-
Chapter and Conference Paper
Parameterized Complexity of DAG Partitioning
The goal of tracking the origin of short, distinctive phrases (memes) that propagate through the web in reaction to current events has been formalized as DAG Partitioning: given a directed acyclic graph, delete e...
-
Chapter and Conference Paper
On Explaining Integer Vectors by Few Homogenous Segments
We extend previous studies on NP-hard problems dealing with the decomposition of nonnegative integer vectors into sums of few homogeneous segments. These problems are motivated by radiation therapy and databas...
-
Chapter and Conference Paper
Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
We study the parameterized complexity of the directed variant of the classical Steiner Tree problem on various classes of directed sparse graphs. While the parameterized complexity of Steiner Tree parameterized b...
-
Chapter and Conference Paper
The Parameterized Complexity of Local Search for TSP, More Refined
We extend previous work on the parameterized complexity of local search for the Travelling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance mea...
-
Chapter and Conference Paper
Clustered Planarity: Clusters with Few Outgoing Edges
We present a linear algorithm for c-planarity testing of clustered graphs, in which every cluster has at most four outgoing edges.
-
Chapter and Conference Paper
Clustered Planarity: Small Clusters in Eulerian Graphs
We present several polynomial-time algorithms for c-planarity testing for clustered graphs with clusters of size at most three. The most general result concerns a special class of Eulerian graphs, namely graph...
