3 papers
math.CO2026
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…
cs.DS2025
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…
cs.DS2024
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…