Geodesic
On the Complexity of Target Set Selection in Simple Geometric Networks
Discrete mathematics & theoretical computer science, Tome 26 (2024) no. 2.

Voir la notice de l'article provenant de la source Episciences

We study the following model of disease spread in a social network. At first, all individuals are either infected or healthy. Next, in discrete rounds, the disease spreads in the network from infected to healthy individuals such that a healthy individual gets infected if and only if a sufficient number of its direct neighbors are already infected. We represent the social network as a graph. Inspired by the real-world restrictions in the current epidemic, especially by social and physical distancing requirements, we restrict ourselves to networks that can be represented as geometric intersection graphs. We show that finding a minimal vertex set of initially infected individuals to spread the disease in the whole network is computationally hard, already on unit disk graphs. Hence, to provide some algorithmic results, we focus ourselves on simpler geometric graph classes, such as interval graphs and grid graphs.
DOI : 10.46298/dmtcs.11591
Classification : 05C82, 68Q17, 91D30, 92D30 
@article{DMTCS_2024_26_2_a9,
     author = {Dvo\v{r}\'ak, Michal and Knop, Du\v{s}an and Schierreich, \v{S}imon},
     title = {On the {Complexity} of {Target} {Set} {Selection} in {Simple} {Geometric} {Networks}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2024},
     doi = {10.46298/dmtcs.11591},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.11591/}
}
TY  - JOUR
AU  - Dvořák, Michal
AU  - Knop, Dušan
AU  - Schierreich, Šimon
TI  - On the Complexity of Target Set Selection in Simple Geometric Networks
JO  - Discrete mathematics & theoretical computer science
PY  - 2024
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.11591/
DO  - 10.46298/dmtcs.11591
LA  - en
ID  - DMTCS_2024_26_2_a9
ER  - 
%0 Journal Article
%A Dvořák, Michal
%A Knop, Dušan
%A Schierreich, Šimon
%T On the Complexity of Target Set Selection in Simple Geometric Networks
%J Discrete mathematics & theoretical computer science
%D 2024
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.11591/
%R 10.46298/dmtcs.11591
%G en
%F DMTCS_2024_26_2_a9
Dvořák, Michal; Knop, Dušan; Schierreich, Šimon. On the Complexity of Target Set Selection in Simple Geometric Networks. Discrete mathematics & theoretical computer science, Tome 26 (2024) no. 2. doi : 10.46298/dmtcs.11591. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.11591/

Cité par Sources :