The complexity of finding effectors

DOI10.1007/s00224-016-9670-8zbMath1362.68102DBLPconf/tamc/BulteauFFNT15arXiv1411.7838OpenAlexW1632976971WikidataQ62039059 ScholiaQ62039059MaRDI QIDQ519899

Vincent Froese, Rolf Niedermeier, Stefan Fafianie, Laurent Bulteau, Nimrod Talmon

Publication date: 31 March 2017

Published in: Lecture Notes in Computer Science, Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.7838

zbMATH Keywords

social networksparameterized complexityexact algorithmsinfluence maximizationnetwork activationprobabilistic information propagation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Treewidth governs the complexity of target set selection
• On the parameterized complexity of multiple-interval graph problems
• Scalable influence maximization for independent cascade model in large-scale social networks
• Parameterized approximability of maximizing the spread of influence in networks
• Constant thresholds can make target set selection tractable
• Parametrized complexity theory.
• Explaining Snapshots of Network Diffusions: Structural and Hardness Results
• On Tractable Cases of Target Set Selection
• The Complexity of Enumeration and Reliability Problems
• Parameterized Inapproximability of Target Set Selection and Generalizations
• Computational Complexity
• Parameterized Algorithms

This page was built for publication: The complexity of finding effectors