33 citations · 93 across the 33 of their papers we have counts for
37 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…
A Simple Algorithm for the Directed Multiple Source Replacement Paths Problem
Kaito Harada, Taisuke Izumi
In the replacement paths (RP) problem, we are given a graph with and , together with two vertices , and are asked to compute the shortes…
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 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,…
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…