• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Parameterized Approximability of Maximizing the Spread of Influence in Networks

Thumbnail
Date
2013
Link to item file
http://arxiv.org/abs/1303.6907v2
Dewey
Recherche opérationnelle
Sujet
TSS
DOI
http://dx.doi.org/10.1007/978-3-642-38768-5_48
Book title
Computing and Combinatorics. 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings
Author
Ding-Zhu Du, Guochuan Zhang
Publisher
Springer
Publisher city
Berlin Heidelberg
Year
2013
ISBN
978-3-642-38767-8
Book URL
10.1007/978-3-642-38768-5
URI
https://basepub.dauphine.fr/handle/123456789/15782
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bazgan, Cristina
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chopin, Morgan
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Nichterlein, André
63094 Berlin University of Technology
Sikora, Florian
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
543-554
Abstract (EN)
In this paper, we consider the problem of maximizing the spread of influence through a social network. Here, we are given a graph G = (V,E), a positive integer k and a threshold value thr(v) attached to each vertex v ∈ V. The objective is then to find a subset of k vertices to “activate” such that the number of activated vertices at the end of a propagation process is maximum. A vertex v gets activated if at least thr(v) of its neighbors are. We show that this problem is strongly inapproximable in fpt-time with respect to (w.r.t.) parameter k even for very restrictive thresholds. For unanimity thresholds, we prove that the problem is inapproximable in polynomial time and the decision version is W[1]-hard w.r.t. parameter k. On the positive side, it becomes r(n)-approximable in fpt-time w.r.t. parameter k for any strictly increasing function r. Moreover, we give an fpt-time algorithm to solve the decision version for bounded degree graphs.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.