Pervasive Domination
Gennaro Cordasco  1, *@  , Luisa Gargano  2@  , Adele Rescigno  2@  
1 : Università della Campania "L.Vanvitelli"
2 : Università di Salerno
* : Corresponding author

Inspired by the implicit or explicit persuasion scenario, which characterizes social media platforms, we analyze a novel domination problem named Pervasive Domination. We consider a social network modeled by a digraph G=(V,E) where an arc (u,v) in E represents the capability of an individual u to persuade an individual v. We are looking for a set S subset V of social change individuals, of minimum cost, who combined enable to reach the desired behavior. The impact of S is measured by a set function f(S). We show that the natural greedy algorithm provides an approximation guarantee, (ln frac{ p-f(emptyset)}{beta}+2 where beta >0 represents the minimum gain on the function f.


Online user: 1 Privacy
Loading...