On the Complexity of Target Set Selection in Simple Geometric Networks

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Complexity of Target Set Selection in Simple Geometric Networks

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On the Complexity of Target Set Selection in Simple Geometric Networks

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-19557S" target="_blank" >GA22-19557S: Nové výzvy ve výpočetní socální volbě</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Mathematics and Theoretical Computer Science

ISSN

1462-7264

e-ISSN

1365-8050

Svazek periodika

26

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

26

Strana od-do

1-26

Kód UT WoS článku

001339628500001

EID výsledku v databázi Scopus

2-s2.0-85203108066