Partial immunization of trees

DOI10.1016/J.DISOPT.2020.100568MaRDI QIDQ2299985zbMATHOpenAlexFDO

Authors Mitre C. Dourado, Stefan Ehard, Dieter Rautenbach, Lucia Draque Penso

Publication date 24 February 2020

Published in Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

vaccinationdynamic monopoly

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: For a graph $G$ and an integer-valued function $au$ on its vertex set, a dynamic monopoly is a set of vertices of $G$ such that iteratively adding to it vertices $u$ of $G$ that have at least $au(u)$ neighbors in it eventually yields the vertex set of $G$. We study the problem of maximizing the minimum order of a dynamic monopoly by increasing the threshold values of individual vertices subject to vertex-dependent lower and upper bounds, and fixing the total increase. We solve this problem efficiently for trees, which extends a result of Khoshkhah and Zaker (On the largest dynamic monopolies of graphs with a given average threshold, Canadian Mathematical Bulletin 58 (2015) 306-316).

Recommendations

• Vaccinate your trees!
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Dynamic monopolies for interval graphs with bounded thresholds

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• Combinatorial model and bounds for target set selection
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
• Epidemics and vaccination on weighted graphs
• Graphs with specified degree distributions, simple epidemics, and local vaccination strategies
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• On the approximability of influence in social networks
• Preventing unraveling in social networks: the anchored \(k\)-core problem
• Remarks on dynamic monopolies with given average thresholds
• Some results on the target set selection problem
• Spread of influence in weighted networks under time and budget constraints
• Treewidth governs the complexity of target set selection
• Triggering cascades on strongly connected directed graphs
• Vaccinate your trees!

Cited in

(3)

• Vaccinate your trees!
• Partial immunization processes
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees

This page was built for publication: Partial immunization of trees

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