7 papers
Broadcasting Agents and Adversary: A new variation on Cops and Robbers
William K. Moses, Amanda Redlich, Frederick Stock
We introduce a new game played on graphs, ``Agents and Adversary". This game is reminiscent of ``Cops and Robbers" but has some fundamental differences. We classify infinite famili…
Sliding Squares in Parallel
Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer +4
We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given square-shaped modules in a (labeled or unlabele…
Super Guarding and Dark Rays in Art Galleries
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +5
We explore an Art Gallery variant where each point of a polygon must be seen by k guards, and guards cannot see through other guards. Surprisingly, even covering convex polygons un…
The Price of Connectivity Augmentation on Planar Graphs
Hugo A. Akitaya, Justin Dallant, Erik D. Demaine +5
Given two classes of graphs, , and a -connected graph , we wish to augment with a smallest cardinality set of new e…
Deltahedral Domes over Equiangular Polygons
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +6
A polyiamond is a polygon composed of unit equilateral triangles, and a generalized deltahedron is a convex polyhedron whose every face is a convex polyiamond. We study a variant w…
Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties & Agents
William K. Moses, Amanda Redlich, Frederick Stock
We revisit the problem of \textsc{Broadcast}, introduced by Das, Giachoudis, Luccio, and Markou [OPODIS, 2020], where agents are initially placed on an node dynamic graph…