Target Set Selection in Dense Graph Classes

DOI10.1137/20M1337624MaRDI QIDQ5062113zbMATH OpenOpenAlexFDO

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

Publication date 15 March 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

parameterized complexitytarget set selectiondense graphsopinion diffusion

Mathematics Subject Classification ID

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

Recommendations

• Target set selection in dense graph classes
• Target set selection in Cartesian product graphs.
• scientific article; zbMATH DE number 7397942
• Target set selection on generalized pancake graphs
• Target set selection parameterized by vertex cover and more
• On tractable cases of target set selection
• On approximating target set selection
• Graph structured sparse subset selection
• Target set selection parameterized by clique-width and maximum threshold
• Some results on the target set selection problem

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 1262783 (Why is no real title available?)
• Algorithmic meta-theorems for restrictions of treewidth
• An application of simultaneous diophantine approximation in combinatorial optimization
• Bootstrap percolation in high dimensions
• Can you beat treewidth?
• Combinatorial model and bounds for target set selection
• Constant thresholds can make target set selection tractable
• Graph minors. II. Algorithmic aspects of tree-width
• Integer Programming with a Fixed Number of Variables
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Latency-bounded target set selection in social networks
• Local majorities, coalitions and monopolies in graphs: A review
• On the approximability of influence in social networks
• On the complexity of k-SAT
• On tractable cases of target set selection
• On tree width, bramble size, and expansion
• Parameterized Algorithms for Modular-Width
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Some results on the target set selection problem
• Spread of influence in weighted networks under time and budget constraints
• Target set selection parameterized by clique-width and maximum threshold
• Treewidth governs the complexity of target set selection
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics

Cited in

(9)

• Parameterized complexity for iterated type partitions and modular-width
• Getting linear time in graphs of bounded neighborhood diversity
• On the complexity of target set selection in simple geometric networks
• Establishing herd immunity is hard even in simple geometric networks
• Graph structured sparse subset selection
• Parameterized complexity of weighted target set selection
• On the computational complexity of graph reconstruction
• Parameterized complexity of weighted target set selection
• Weighted target set selection on trees and cycles

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

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