We study variants of the Target Set Selection problem, first proposed by Kempe et al. In our scenario one is given a graph G = (V,E), integer values t(v) for each vertex v, and the objective is to determine a small set of vertices (target set) that activates a given number (or a given subset) of vertices of G within a prescribed number of rounds. The activation process in G proceeds as follows: initially, at round 0, all vertices in the target set are activated; subsequently at each round r ≥ 1 every vertex of G becomes activated if at least t(v) of its neighbors are active by round r − 1. It is known that the problem of finding a minimum cardinality Target Set that eventually activates the whole graph G is hard to approximate to a factor better than O(2log1−ϵ∣∣V∣∣) . In this paper we give exact polynomial time algorithms to find minimum cardinality Target Sets in graphs of bounded clique-width, and exact linear time algorithms for trees.

Latency-Bounded Target Set Selection in Social Networks

GARGANO, Luisa;VACCARO, Ugo
2013

Abstract

We study variants of the Target Set Selection problem, first proposed by Kempe et al. In our scenario one is given a graph G = (V,E), integer values t(v) for each vertex v, and the objective is to determine a small set of vertices (target set) that activates a given number (or a given subset) of vertices of G within a prescribed number of rounds. The activation process in G proceeds as follows: initially, at round 0, all vertices in the target set are activated; subsequently at each round r ≥ 1 every vertex of G becomes activated if at least t(v) of its neighbors are active by round r − 1. It is known that the problem of finding a minimum cardinality Target Set that eventually activates the whole graph G is hard to approximate to a factor better than O(2log1−ϵ∣∣V∣∣) . In this paper we give exact polynomial time algorithms to find minimum cardinality Target Sets in graphs of bounded clique-width, and exact linear time algorithms for trees.
978-3-642-39052-4
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/4008052
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 29
social impact