Open access
Date
2022Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
We consider a special variant of a pursuit-evasion game called lions and contamination. In a graph whose vertices are originally contaminated, a set of lions walk around the graph and clear the contamination from every vertex they visit. The contamination, however, simultaneously spreads to any adjacent vertex not occupied by a lion. We study the relationship between different types of clearings of graphs, such as clearings which do not allow recontamination, clearings where at most one lion moves at each time step and clearings where lions are forbidden to be stacked on the same vertex. We answer several questions raised by Adams et al. [2]. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000557704Publication status
publishedExternal links
Book title
18th Scandinavian Symposium and Workshops on Algorithm TheoryJournal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikEvent
Subject
Algorithmic Games; Pursuit-Evasion Games; Graph Contamination; ClearingsOrganisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
More
Show all metadata
ETH Bibliography
yes
Altmetrics