On tractable cases of target set selection

DOI10.1007/978-3-642-17517-6_34MaRDI QIDQ3060749zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Treewidth governs the complexity of target set selection
• Constant thresholds can make target set selection tractable
• Constant thresholds can make target set selection tractable
• On approximating target set selection
• Latency-bounded target set selection in social networks

Cited in

(25)

• Discovering small target sets in social networks: a fast and effective algorithm
• Active influence spreading in social networks
• Some results on the target set selection problem
• On some tractable and hard instances for partial incentives and target set selection
• On reconfigurability of target sets
• Target set selection on generalized pancake graphs
• Parameterized approximability of maximizing the spread of influence in networks
• Constant thresholds can make target set selection tractable
• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• Evangelism in social networks
• On irreversible spread of influence in edge-weighted graphs
• Target set selection in Cartesian product graphs.
• A fast and effective heuristic for discovering small target sets in social networks
• Target Set Selection in Dense Graph Classes
• Target set selection in dense graph classes
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Grundy Distinguishes Treewidth from Pathwidth
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Enhancing Target Group Selection Using Belief Functions
• Grundy distinguishes treewidth from pathwidth
• Establishing herd immunity is hard even in simple geometric networks
• Weighted target set selection on trees and cycles
• Target set selection with maximum activation time
• On the complexity of target set selection in simple geometric networks
• Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available

This page was built for publication: On tractable cases of target set selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3060749)