License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.17
URN: urn:nbn:de:0030-drops-161778
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16177/
Go to the corresponding LIPIcs Volume Portal

Bertschinger, Daniel ; M. Reddy, Meghana ; Mann, Enrico

Lions and Contamination: Monotone Clearings

pdf-format:
LIPIcs-SWAT-2022-17.pdf (0.7 MB)

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. [H. Adams et al., 2020].

BibTeX - Entry

@InProceedings{bertschinger_et_al:LIPIcs.SWAT.2022.17,
  author =	{Bertschinger, Daniel and M. Reddy, Meghana and Mann, Enrico},
  title =	{{Lions and Contamination: Monotone Clearings}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{17:1--17:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16177},
  URN =		{urn:nbn:de:0030-drops-161778},
  doi =		{10.4230/LIPIcs.SWAT.2022.17},
  annote =	{Keywords: Algorithmic Games, Pursuit-Evasion Games, Graph Contamination, Clearings}
}

Keywords: Algorithmic Games, Pursuit-Evasion Games, Graph Contamination, Clearings
Collection: 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Issue Date: 2022
Date of publication: 22.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI