Vaccinate your trees!

DOI10.1016/J.TCS.2018.11.018MaRDI QIDQ2632015zbMATHOpenAlexFDO

Authors Stefan Ehard, Dieter Rautenbach

Publication date 17 May 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

vaccinationdynamic monopoly

Mathematics Subject Classification ID

Applications of graph theory (05C90) Microeconomic theory (price theory and economic markets) (91B24)

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 two vaccination problems, where the goal is to maximize the minimum order of such a dynamic monopoly either by increasing the threshold value of $b$ vertices beyond their degree, or by removing $b$ vertices from $G$, where $b$ is a given non-negative integer corresponding to a budget. We show how to solve these problems efficiently for trees.

Recommendations

• Partial immunization of trees
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
• On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
• On dynamic monopolies of graphs with general 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

Cited in

(3)

• Partial immunization of trees
• Parameterized complexity of immunization in the threshold model
• Immunization in the threshold model: a parameterized complexity study

This page was built for publication: Vaccinate your trees!

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