Constant thresholds can make target set selection tractable

DOI10.1007/978-3-642-34862-4_9MaRDI QIDQ4916038zbMATH OpenOpenAlexFDO

Authors Morgan Chopin, André Nichterlein, Rolf Niedermeier, Mathias Weller

Publication date 19 April 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.377.3067

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30)

Recommendations

• Constant thresholds can make target set selection tractable
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Parameterized inapproximability of target set selection and generalizations
• Parameterized inapproximability of target set selection and generalizations

Cited in

(16)

• On some tractable and hard instances for partial incentives and target set selection
• Parameterized approximability of maximizing the spread of influence in networks
• Constant thresholds can make target set selection tractable
• Fast and frugal targeting with incentives
• Influence diffusion in social networks under time window constraints
• Spread of influence in weighted networks under time and budget constraints
• Latency-bounded target set selection in social networks
• Exact solutions for latency-bounded target set selection problem on some special families of graphs
• Influence Diffusion in Social Networks under Time Window Constraints
• On tractable cases of target set selection
• Optimizing spread of influence in social networks via partial incentives
• A fast and effective heuristic for discovering small target sets in social networks
• Parameterized inapproximability of target set selection and generalizations
• Parameterized complexity of weighted target set selection
• Parameterized complexity of weighted target set selection
• Complexity analysis of P₃-convexity problems on bounded-degree and planar graphs

This page was built for publication: Constant thresholds can make target set selection tractable

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