Firefighting on square, hexagonal, and triangular grids

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10282423" target="_blank" >RIV/00216208:11320/14:10282423 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.disc.2014.06.020" target="_blank" >http://dx.doi.org/10.1016/j.disc.2014.06.020</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.disc.2014.06.020" target="_blank" >10.1016/j.disc.2014.06.020</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Firefighting on square, hexagonal, and triangular grids

Popis výsledku v původním jazyce

In this paper, we consider the firefighter problem on a graph G = (V, E) that is either finite or infinite. Suppose that a fire breaks out at a given vertex v is an element of V. In each subsequent time unit, a firefighter protects one vertex which is not yet on fire, and then the fire spreads to all unprotected neighbors of the vertices on fire. The objective of the firefighter is to save as many vertices as possible (if G is finite) or to stop the fire from spreading (for an infinite case). The surviving rate rho(G) of a finite graph G is defined as the expected percentage of vertices that can be saved when a fire breaks out at a vertex of G that is selected uniformly random. For a finite square grid P-n square P-n, we show that 5/8 + 0(1) {= rho(P-nsquare P-n) {= 67 243/105 300 + 0(1) (leaving the gap smaller than 0.0136) and conjecture that the surviving rate is asymptotic to 5/8. We define the surviving rate for infinite graphs and prove it to be 1/4 for the infinite square grid,

Název v anglickém jazyce

Firefighting on square, hexagonal, and triangular grids

Popis výsledku anglicky

In this paper, we consider the firefighter problem on a graph G = (V, E) that is either finite or infinite. Suppose that a fire breaks out at a given vertex v is an element of V. In each subsequent time unit, a firefighter protects one vertex which is not yet on fire, and then the fire spreads to all unprotected neighbors of the vertices on fire. The objective of the firefighter is to save as many vertices as possible (if G is finite) or to stop the fire from spreading (for an infinite case). The surviving rate rho(G) of a finite graph G is defined as the expected percentage of vertices that can be saved when a fire breaks out at a vertex of G that is selected uniformly random. For a finite square grid P-n square P-n, we show that 5/8 + 0(1) {= rho(P-nsquare P-n) {= 67 243/105 300 + 0(1) (leaving the gap smaller than 0.0136) and conjecture that the surviving rate is asymptotic to 5/8. We define the surviving rate for infinite graphs and prove it to be 1/4 for the infinite square grid,

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

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

Rok uplatnění

2014

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

ISSN

0012-365X

e-ISSN

—

Svazek periodika

337

Číslo periodika v rámci svazku

December

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

14

Strana od-do

142-155

Kód UT WoS článku

000343843300013

EID výsledku v databázi Scopus

—