Vaccinate your trees!

DOI10.1016/J.TCS.2018.11.018zbMATH Open1426.91118arXiv1801.08705OpenAlexW2963991513MaRDI QIDQ2632015FDOQ2632015

Authors: Stefan Ehard, Dieter Rautenbach 

Publication date: 17 May 2019

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

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.

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

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

zbMATH Keywords

vaccinationdynamic monopoly

Mathematics Subject Classification ID

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

Cites Work

• Some results on the target set selection problem
• On the approximability of influence in social networks
• Combinatorial model and bounds for target set selection
• Treewidth governs the complexity of target set selection
• Title not available (Why is that?)
• 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
• Epidemics and vaccination on weighted graphs
• Triggering cascades on strongly connected directed graphs
• Remarks on dynamic monopolies with given average thresholds
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
• Graphs with specified degree distributions, simple epidemics, and local vaccination strategies
• Spread of influence in weighted networks under time and budget constraints
• Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem

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)