Deciding a Graph Property by a Single Mobile Agent: One-Bit Memory Suffices

Taisuke Izumi, Kazuki Kakizawa, Yuya Kawabata +2

We investigate the computational power of the deterministic single-agent model where the agent and each node are equipped with a limited amount of persistent memory. Tasks are form…