Target Set Selection in Dense Graph Classes

DOI10.1137/20M1337624OpenAlexW4214527898MaRDI QIDQ5062113

Pavel Dvořák, Tomáš Toufar, Dušan Knop

Publication date: 15 March 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.07530

zbMATH Keywords

target set selectionparameterized complexitydense graphsopinion diffusion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Establishing herd immunity is hard even in simple geometric networks ⋮ Parameterized complexity for iterated type partitions and modular-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial model and bounds for target set selection
• Treewidth governs the complexity of target set selection
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• An application of simultaneous diophantine approximation in combinatorial optimization
• Local majorities, coalitions and monopolies in graphs: A review
• Algorithmic meta-theorems for restrictions of treewidth
• Some results on the target set selection problem
• Constant thresholds can make target set selection tractable
• Spread of influence in weighted networks under time and budget constraints
• Latency-bounded target set selection in social networks
• On tree width, bramble size, and expansion
• Parameterized Algorithms for Modular-Width
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Integer Programming with a Fixed Number of Variables
• On Tractable Cases of Target Set Selection
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• On the Approximability of Influence in Social Networks
• Graph minors. II. Algorithmic aspects of tree-width
• Bootstrap Percolation in High Dimensions
• Target Set Selection Parameterized by Clique-Width and Maximum Threshold
• On the complexity of \(k\)-SAT

This page was built for publication: Target Set Selection in Dense Graph Classes