From the 1 of 7 linked papers with an AI index.
1 citations · 1 across the 3 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…
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…
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…
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…
Fully Adaptive Self-Stabilizing Transformer for LCL Problems
Shimon Bitton, Yuval Emek, Taisuke Izumi +1
The first generic self-stabilizing transformer for local problems in a constrained bandwidth model is introduced. This transformer can be applied to a wide class of locally checkab…