Publications

Authors:

Cicalese, Ferdinando; Gennaro, Cordasco; Luisa, Gargano; Martin, Milanic; Ugo, Vaccaro

Title:

Latency-bounded target set selection in social networks

Year:

2014

Type of item:

Articolo in Rivista

Tipologia ANVUR:

Articolo su rivista

Language:

Inglese

Format:

A Stampa

Referee:

Sì

Name of journal:

Theoretical Computer Science

ISSN of journal:

0304-3975

N° Volume:

535

:

Elsevier

Page numbers:

1-15

Keyword:

Target set selection; Monotone irreversible dynamic monopolies (dynamo)

Short description of contents:

Motivated by applications in sociology, economy and medicine, we study variants of the Target Set Selection problem, first proposed by Kempe, Kleinberg and Tardos. In our scenario one is given a graph G=(V,E), integer values t(v) for each vertex v (thresholds), 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 already 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.

Web page:

http://www.sciencedirect.com/science/article/pii/S0304397514001339

Product ID:

85579

Handle IRIS:

11562/881274

Deposited On:

January 30, 2015

Last Modified:

November 11, 2022

Bibliographic citation:

Cicalese, Ferdinando; Gennaro, Cordasco; Luisa, Gargano; Martin, Milanic; Ugo, Vaccaro, Latency-bounded target set selection in social networks «Theoretical Computer Science» , vol. 535 , 2014 , pp. 1-15

Consulta la scheda completa presente nel repository istituzionale della Ricerca di Ateneo