31 citations · 59 across the 7 of their papers we have counts for
8 papers
Toward Scalable Algorithms for the Unsplittable Shortest Path Routing Problem
Amal Benhamiche, Morgan Chopin
In this paper, we consider the Delay Constrained Unsplittable Shortest Path Routing problem which arises in the field of traffic engineering for IP networks. This problem consists,…
Fixed-Parameter Algorithms for DAG Partitioning
René van Bevern, Robert Bredereck, Morgan Chopin +4
Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM SIGKDD 2009] as DAG Partitioning: given an arc-weighted directed acyclic…
Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms
Faisal N. Abu-Khzam, Cristina Bazgan, Morgan Chopin +1
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 s…
Parameterized Inapproximability of Target Set Selection and Generalizations
Cristina Bazgan, Morgan Chopin, André Nichterlein +1
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value for any vertex of the graph, find a minimum size vertex-subset to "act…
Structural parameterizations for boxicity
Henning Bruhn, Morgan Chopin, Felix Joos +1
The boxicity of a graph is the least integer such that has an intersection model of axis-aligned -dimensional boxes. Boxicity, the problem of deciding whether a give…
The Firefighter Problem: A Structural Analysis
Janka Chlebíková, Morgan Chopin
We consider the complexity of the firefighter problem where b>=1 firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most th…
Parameterized Approximability of Maximizing the Spread of Influence in Networks
Cristina Bazgan, Morgan Chopin, André Nichterlein +1
In this paper, we consider the problem of maximizing the spread of influence through a social network. Given a graph with a threshold value~ attached to each vertex~, th…
The firefighter problem with more than one firefighter on trees
Cristina Bazgan, Morgan Chopin, Bernard Ries
In this paper we study the complexity of the firefighter problem and related problems on trees when more than one firefighter is available at each time step, and answer several ope…