-
Chapter and Conference Paper
A Multi-Agent Based Dynamic Network Slice Tarification Framework
5G networks promise to satisfy diverse kinds of advanced use cases, by providing tailored services to different kinds of customers, through the concept of Network Slicing (NS). Although NS, i.e. multiple virtu...
-
Chapter and Conference Paper
Monte Carlo Search Algorithms for Network Traffic Engineering
The aim of Traffic Engineering is to provide routing configurations in networks such that the used resources are minimized while maintaining a high level of quality of service (QoS). Among the optimization pro...
-
Article
Structural Parameterizations for Boxicity
The boxicity of a graph G is the least integer d such that G has an intersection model of axis-aligned d-dimensional boxes. Boxicity, the problem of deciding whether a given graph G has boxicity at most d, is NP-...
-
Article
Constant Thresholds Can Make Target Set Selection Tractable
Target Set Selection, which is a prominent NP-hard problem occurring in social network analysis and distributed computing, is notoriously hard both in terms of achieving useful polynomial-time ap...
-
Chapter and Conference Paper
Parameterized Inapproximability of Target Set Selection and Generalizations
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value for each vertex v of the graph, find a minimum...
-
Chapter and Conference Paper
Approximation Algorithms Inspired by Kernelization Methods
Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining...
-
Chapter and Conference Paper
The Firefighter Problem: A Structural Analysis
We consider the complexity of the firefighter problem where a budget of \({b \ge 1}\) firefighters are available at each time s...
-
Chapter and Conference Paper
Structural Parameterizations for Boxicity
The boxicity of a graph \(G\) is the least integer \(d\) such ...
-
Chapter and Conference Paper
Parameterized Approximability of Maximizing the Spread of Influence in Networks
In this paper, we consider the problem of maximizing the spread of influence through a social network. Here, we are given a graph G = (V,E), a positive integer k and a threshold value thr(v) attached to each vert...
-
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
The Robust Set Problem: Parameterized Complexity and Approximation
In this paper, we introduce the Robust Set problem: given a graph G = (V,E), a threshold function t:V → N and an integer k, find a subset of vertices V′ ⊆ V of size at least k such that every vertex v in G has le...
-
Chapter and Conference Paper
Constant Thresholds Can Make Target Set Selection Tractable
Target Set Selection, which is a prominent NP-hard problem occurring in social network analysis and distributed computing, is notoriously hard both in terms of achieving useful approximation as wel...
-
Chapter and Conference Paper
Parameterized Complexity of the Firefighter Problem
In this paper we study the parameterized complexity of the firefighter problem. More precisely, we show that Saving k -Vertices and its dual Saving All But k ...
