4 papers
Color Complexity of Recolorable Graph Exploration: Upper and Lower Bounds via Block Structure
Shoma Hiraoka, Shunsuke Imori, Shota Takahashi +1
We study exploration of anonymous, port-free graphs by a single agent with no internal memory. To compensate for the lack of memory, the agent uses writable vertex colors as extern…
Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors
Shota Takahashi, Haruki Kanaya, Shoma Hiraoka +2
Recently, Böckenhauer, Frei, Unger, and Wehner (SIROCCO 2023) introduced a novel variant of the graph exploration problem in which a single memoryless agent must visit all nodes of…
Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents
Jion Hirose, Ryota Eguchi, Yuichi Sudo
We study the \emph{Byzantine} gathering problem involving mobile agents with unique identifiers (IDs), of which are Byzantine. These agents start the execution of a common…
Complete Graph Identification in Population Protocols
Haruki Kanaya, Yuichi Sudo
We consider the population protocol model where indistinguishable state machines, referred to as agents, communicate in pairs. The communication graph specifies potential interacti…