4 papers
A Linear-Time Algorithm for Finding an Odd/Even Cycle Through Two Specified Vertices
Takumi Kano, Yutaro Yamaguchi
We present a deterministic linear-time algorithm for finding an odd/even cycle through two specified vertices in an undirected graph. This is shown in a generalized form as follows…
A hierarchy of edge-weight symmetries in perfect matchings
Kristóf Bérczi, Viktor Csaplár, Yutaro Yamaguchi
Motivated by the exact weight perfect matching problem and recent parameterized algorithms for finding an -th smallest perfect matching, we study structural properties of edg…
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…