3 citations · 5 across the 13 of their papers we have counts for
15 papers
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…
Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation
Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi
Finding a maximum cardinality matching in a graph is one of the most fundamental problems. An algorithm proposed by Micali and Vazirani (1980) is well-known to solve the problem in…
Independent Set Reconfiguration Under Bounded-Hop Token
Hiroki Hatano, Naoki Kitamura, Taisuke Izumi +2
The independent set reconfiguration problem (ISReconf) is the problem of determining, for given independent sets I_s and I_t of a graph G, whether I_s can be transformed into I_t b…
A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
Kaito Harada, Naoki Kitamura, Taisuke Izumi +1
An \emph{-approximate vertex fault-tolerant distance sensitivity oracle} (\emph{-VSDO}) for a weighted input graph and a source vertex is the data str…
A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi
In this paper, we propose a randomized -round algorithm for the maximum cardinality matching problem in the CONGEST model, where means the maximum size of a…
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…
Fast Neighborhood Rendezvous
Ryota Eguchi, Naoki Kitamura, Taisuke Izumi
In the rendezvous problem, two computing entities (called \emph{agents}) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the sy…
A Subquadratic-Time Distributed Algorithm for Exact Maximum Matching
Naoki Kitamura, Taisuke Izumi
For a graph G=(V,E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the t…
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…