8 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…
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…
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…