-
Article
Cluster Editing for Multi-Layer and Temporal Graphs
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-Layer Cluster Editing we receive ...
-
Chapter and Conference Paper
Preparation of Glass Sampling Containers to Determine Trace Amounts of Accelerants in Fire Samples
Gas chromatography is be used to prove the presence of small amounts of organics trapped on solid samples or in liquid samples from fires and it serves as evidence of the presence of traces of flammable liquid...
-
Article
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
Generating Faster Algorithms for d-Path Vertex Cover
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 themselves doing a meticulous analys...
-
Article
Open AccessA Parameterized Complexity View on Collapsing k-Cores
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 graph, that is, the (uniquely d...
-
Chapter and Conference Paper
Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Consider a vertex-weighted graph G with a source s and a target t. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique...
-
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...
-
Article
Open AccessA Tight Lower Bound for Planar Steiner Orientation
In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs ...
-
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...
-
Article
Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices
In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph con...
-
Article
A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
We study the problem of non-preemptively scheduling n jobs, each job j with a release time \(t_j\) ...
-
Chapter and Conference Paper
A Simple Streaming Bit-Parallel Algorithm for Swap Pattern Matching
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 algorithm that takes advantage...
-
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)\) ...
-
Article
On the Parameterized Complexity of Computing Balanced Partitions in Graphs
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 the vertices into two equal-sized...
-
Chapter and Conference Paper
Solving Multicut Faster Than 2 n
In the Multicut problem, we are given an undirected graph G = (V,E) and a family \(\mathcal{T} = \{({s_i}{t_i}) \mid s_i, t_i \in V\}\) ...
-
Article
The Parameterized Complexity of Local Search for TSP, More Refined
We extend previous work on the parameterized complexity of local search for the Traveling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance meas...
-
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
An FPT Algorithm for Tree Deletion Set
We give a 5 k n O(1) fixed-parameter algorithm for determining whether a given undirected graph on n vertices has a subset of ...
-
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
A Refined Complexity Analysis of Degree Anonymization in Graphs
Motivated by a strongly growing interest in graph anonymization in the data mining and databases communities, we study the NP-hard problem of making a graph k-anonymous by adding as few edges as possible. Herein,...
