From the 2 of 7 linked papers with an AI index.
1 citations · 1 across the 4 of their papers we have counts for
7 papers
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
The paper presents a card‑based cryptographic protocol that lets players run the social deduction game Werewolf without a trusted moderator, using public card operations that give…
Improved Algorithms for Local Failover Routing on Directed Graphs
Yuki Kawashima, Naoki Kitamura, Taisuke Izumi
The paper presents new algorithms for local failover routing on directed graphs that minimize the number of rewritable bits needed in packet headers to handle up to k arc failures,…
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…
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…