Document Open Access Logo

Lions and Contamination: Monotone Clearings

Authors Daniel Bertschinger, Meghana M. Reddy, Enrico Mann

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.17.pdf
  • Filesize: 0.68 MB
  • 11 pages

Document Identifiers

Author Details

Daniel Bertschinger
  • Department of Computer Science, ETH Zürich, Switzerland
Meghana M. Reddy
  • Department of Computer Science, ETH Zürich, Switzerland
Enrico Mann
  • Department of Computer Science, ETH Zürich, Switzerland

Funding

  • M. Reddy, Meghana: Supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681.

Cite AsGet BibTex

Daniel Bertschinger, Meghana M. Reddy, and Enrico Mann. Lions and Contamination: Monotone Clearings. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 17:1-17:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.17

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

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • Algorithmic Games
  • Pursuit-Evasion Games
  • Graph Contamination
  • Clearings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. Adams and G. Carlsson. Evasion paths in mobile sensor networks. The International Journal of Robotics Research, 34(1):90-104, 2015. URL: https://doi.org/10.1177/0278364914548051.
  2. H. Adams, L. Gibson, and J. Pfaffinger. Lions and contamination, triangular grids, and cheeger constants. arXiv, 2020. URL: http://arxiv.org/abs/2012.06702.
  3. F. Berger, A. Gilbers, A. Grüne, and R. Klein. How many lions are needed to clear a grid? Algorithms, 2(3):1069-1086, 2009. URL: https://doi.org/10.3390/a2031069.
  4. A. Bonato and B. Yang. Graph searching and related problems. In P. M. Pardalos, D.-Z. Du, and R. L. Graham, editors, Handbook of Combinatorial Optimization, pages 1511-1558, 2013. URL: https://doi.org/10.1007/978-1-4419-7997-1_76.
  5. R. Borie, S. Koenig, and C. Tovey. Section 9.5: Pursuit-evasion problems. In J. Yellen J. Gross and P. Zhang, editors, Handbook of Graph Theory, pages 1145-1165. Chapman and Hall/CRC, 2013. Google Scholar
  6. P. Brass, K. D. Kim, H.-S. Na, and C.-S. Shin. Escaping off-line searchers and a discrete isoperimetric theorem. In Algorithms and Computation, pages 65-74, 2007. Google Scholar
  7. T. H. Chung, G. A. Hollinger, and V. Isler. Search and pursuit-evasion in mobile robotics, a survey, 2011. URL: https://calhoun.nps.edu/handle/10945/45474.
  8. V. de Silva and R. Ghrist. Coordinate-free coverage in sensor networks with controlled boundaries via homology. The International Journal of Robotics Research, 25(12):1205-1222, 2006. URL: https://doi.org/10.1177/0278364906072252.
  9. A. Dumitrescu, I. Suzuki, and P. Zylinski. Offline variants of the "lion and man" problem. In Proceedings of the Twenty-Third Annual Symposium on Computational Geometry, pages 102-111. Association for Computing Machinery, 2007. URL: https://doi.org/10.1145/1247069.1247085.
  10. F. V. Fomin and D. M. Thilikos. An annotated bibliography on guaranteed graph searching. Theoretical Computer Science, 399(3):236-245, 2008. Graph Searching. URL: https://doi.org/10.1016/j.tcs.2008.02.040.
  11. R. Isaacs. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. John Wiley & Sons, 1965. Google Scholar
  12. A. S. LaPaugh. Recontamination does not help to search a graph. J. ACM, 40(2):224-245, 1993. URL: https://doi.org/10.1145/151261.151263.
  13. S. M. LaValle and S. A. Hutchinson. Optimal motion planning for multiple robots having independent goals. IEEE Transactions on Robotics and Automation, 14(6):912-925, 1998. URL: https://doi.org/10.1109/70.736775.
  14. T. D. Parsons. Pursuit-evasion in a graph. In Y. Alavi and D. R. Lick, editors, Theory and Applications of Graphs, pages 426-441, 1978. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact