31 citations · 59 across the 7 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.DM2013
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…
cs.DS2013★ 31 cited
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…