Partial immunization of trees

DOI10.1016/J.DISOPT.2020.100568zbMATH Open1506.05157arXiv1802.03754OpenAlexW3004663040MaRDI QIDQ2299985FDOQ2299985

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

Publication date: 24 February 2020

Published in: Discrete Optimization (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 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).

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

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

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)

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
• Vaccinate your trees!

Cited In (1)

• Partial immunization processes

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)