2 Search Results for "Shermer, Thomas"

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.56
Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor

Authors: Prosenjit Bose, Jean-Lou De Carufel, and Thomas Shermer

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We study zombies and survivor, a variant of the game of cops and robber on graphs. In this variant, the single survivor plays the role of the robber and attempts to escape from the zombies that play the role of the cops. The zombies are restricted, on their turn, to always follow an edge of a shortest path towards the survivor. Let z(G) be the smallest number of zombies required to catch the survivor on a graph G with n vertices. We show that there exist outerplanar graphs and visibility graphs of simple polygons such that z(G) = Θ(n). We also show that there exist maximum-degree-3 outerplanar graphs such that z(G) = Ω(n/log(n)). Let z_L(G) be the smallest number of lazy zombies (zombies that can stay still on their turn) required to catch the survivor on a graph G. We show that lazy zombies are more powerful than normal zombies but less powerful than cops. We prove that z_L(G) ≤ 2 for connected outerplanar graphs and this bound is tight in the worst case. We show that z_L(G) ≤ k for connected graphs with treedepth k. This result implies that z_L(G) is at most (k+1)log n for connected graphs with treewidth k, O(√n) for connected planar graphs, O(√{gn}) for connected graphs with genus g and O(h√{hn}) for connected graphs with any excluded h-vertex minor. Our results on lazy zombies still hold when an adversary chooses the initial positions of the zombies.
Cite as

Prosenjit Bose, Jean-Lou De Carufel, and Thomas Shermer. Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 56:1-56:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.ISAAC.2022.56,
  author =	{Bose, Prosenjit and De Carufel, Jean-Lou and Shermer, Thomas},
  title =	{{Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{56:1--56:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.56},
  URN =		{urn:nbn:de:0030-drops-173418},
  doi =		{10.4230/LIPIcs.ISAAC.2022.56},
  annote =	{Keywords: Pursuit-evasion games, Outerplanar, Graphs, Treedepth, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.13
Gathering by Repulsion

Authors: Prosenjit Bose and Thomas C. Shermer

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
We consider a repulsion actuator located in an n-sided convex environment full of point particles. When the actuator is activated, all the particles move away from the actuator. We study the problem of gathering all the particles to a point. We give an O(n^2) time algorithm to compute all the actuator locations that gather the particles to one point with one activation, and an O(n) time algorithm to find a single such actuator location if one exists. We then provide an O(n) time algorithm to place the optimal number of actuators whose sequential activation results in the gathering of the particles when such a placement exists.
Cite as

Prosenjit Bose and Thomas C. Shermer. Gathering by Repulsion. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.SWAT.2018.13,
  author =	{Bose, Prosenjit and Shermer, Thomas C.},
  title =	{{Gathering by Repulsion}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{13:1--13:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.13},
  URN =		{urn:nbn:de:0030-drops-88397},
  doi =		{10.4230/LIPIcs.SWAT.2018.13},
  annote =	{Keywords: polygon, kernel, beacon attraction}
}
  • Refine by Author
  • 2 Bose, Prosenjit
  • 1 De Carufel, Jean-Lou
  • 1 Shermer, Thomas
  • 1 Shermer, Thomas C.

  • Refine by Classification
  • 2 Mathematics of computing → Graph theory
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Graphs
  • 1 Outerplanar
  • 1 Pursuit-evasion games
  • 1 Treedepth
  • 1 Treewidth
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2022

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