On Tractable Cases of Target Set Selection

DOI10.1007/978-3-642-17517-6_34zbMath1310.68115OpenAlexW1486147625MaRDI QIDQ3060749

Johannes Uhlmann, Rolf Niedermeier, Mathias Weller, André Nichterlein

Publication date: 9 December 2010

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-17517-6_34

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (19)

Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available ⋮ Discovering small target sets in social networks: a fast and effective algorithm ⋮ Target Set Selection in Dense Graph Classes ⋮ A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks ⋮ An Adaptive Version of Brandes' Algorithm for Betweenness Centrality ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Target set selection with maximum activation time ⋮ Unnamed Item ⋮ An Adaptive Version of Brandes' Algorithm for Betweenness Centrality ⋮ Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks ⋮ Active influence spreading in social networks ⋮ The complexity of finding effectors ⋮ Parameterized approximability of maximizing the spread of influence in networks ⋮ Unnamed Item ⋮ Whom to befriend to influence people ⋮ Evangelism in Social Networks ⋮ On irreversible spread of influence in edge-weighted graphs ⋮ On reconfigurability of target sets

This page was built for publication: On Tractable Cases of Target Set Selection