On the Complexity of Target Set Selection in Simple Geometric Networks
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00375755" target="_blank" >RIV/68407700:21240/24:00375755 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.46298/dmtcs.11591" target="_blank" >https://doi.org/10.46298/dmtcs.11591</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.46298/dmtcs.11591" target="_blank" >10.46298/dmtcs.11591</a>
Alternative languages
Result language
angličtina
Original language name
On the Complexity of Target Set Selection in Simple Geometric Networks
Original language description
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 recent 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA22-19557S" target="_blank" >GA22-19557S: New Frontiers in Computational Social Choice</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Discrete Mathematics and Theoretical Computer Science
ISSN
1462-7264
e-ISSN
1365-8050
Volume of the periodical
26
Issue of the periodical within the volume
2
Country of publishing house
FR - FRANCE
Number of pages
26
Pages from-to
1-26
UT code for WoS article
001339628500001
EID of the result in the Scopus database
2-s2.0-85203108066