3 citations · 5 across the 13 of their papers we have counts for
5 papers · 1 filter
Beating Quadratic Time--Message Trade-off in Distributed Minimum Spanning Tree Construction
Taisuke Izumi, Naoki Kitamura, Toshimitsu Masuzawa
We present a new distributed algorithm for computing a minimum spanning tree (MST) in the \textsf{CONGEST-KT} model, where messages are limited to bits and each v…
NP-Hardness of Connected Components Reconfiguration under Component Jumping on Caterpillar Graphs
Naoki Kitamura, Seitaro Kawaguchi, Yuya Terashima +1
We study the Connected Components Reconfiguration problem (CCR), in which connected components on a graph are transformed according to a specified reconfiguration rule. CCR general…
A Moderatorless Protocol for WEREWOLF
Naoki Kitamura, Hironori Kiya, Hirotaka Ono
Social deduction games, or hidden-role games, are multiplayer games in which players are assigned private roles and act under asymmetric information about other players' roles and…
Improved Algorithms for Local Failover Routing on Directed Graphs
Yuki Kawashima, Naoki Kitamura, Taisuke Izumi
The local failover routing is a mechanism that routes a packet from a source to a destination only using pre-calculated routing tables, even when several edges fail. In this paper,…
Tight Bounds on Window Size and Time for Single-Agent Graph Exploration under T-Interval Connectivity
Yuichi Sudo, Naoki Kitamura, Masahiro Shibata +4
We study deterministic exploration by a single agent in -interval-connected graphs, a standard model of dynamic networks in which, for every time window of length , the inter…