4 papers · 1 filter
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…
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…
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…
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…