Hardness Results for Seeding Complex Contagion with Neighborhoods

DOI10.1007/978-3-030-93413-2_18zbMath1504.91211OpenAlexW4206733169MaRDI QIDQ5050309

Ulrik Brandes, Meher Chaitanya

Publication date: 15 November 2022

Published in: Complex Networks & Their Applications X (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-93413-2_18

zbMATH Keywords

computational complexitysocial influencecomplex contagion

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New bounds for contagious sets
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Local majorities, coalitions and monopolies in graphs: A review
• Constant thresholds can make target set selection tractable
• An analysis of approximations for maximizing submodular set functions—I
• On Approximating Target Set Selection
• Automata, Languages and Programming

This page was built for publication: Hardness Results for Seeding Complex Contagion with Neighborhoods