The complexity of finding effectors
DOI10.1007/s00224-016-9670-8zbMath1362.68102arXiv1411.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
social networksparameterized complexityexact algorithmsinfluence maximizationnetwork activationprobabilistic information propagation
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