4 papers
Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs
Taichi Inoue, Naoki Kitamura, Taisuke Izumi +1
We investigated the computational power of a single mobile agent in an -node graph with storage (i.e., node memory). Generally, a system with one-bit agent memory and -bit…
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…
Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs
Taisuke Izumi, Naoki Kitamura, Takamasa Naruse +1
We consider global problems, i.e. problems that take at least diameter time, even when the bandwidth is not restricted. We show that all problems considered admit efficient solutio…
Low-Congestion Shortcut and Graph Parameters
Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi +1
The concept of low-congestion shortcuts is initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologi…