1 citations · 1 across the 6 of their papers we have counts for
6 papers
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…
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…
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…
An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
Hitoshi Murakami, Yutaro Yamaguchi
The exact matching problem is a constrained variant of the maximum matching problem: given a graph with each edge having a weight or and an integer , the goal is to find…
Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
Ryoma Norose, Yutaro Yamaguchi
Finding a minimum-weight strongly connected spanning subgraph of an edge-weighted directed graph is equivalent to the weighted version of the well-known strong connectivity augment…
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…