1 citations · 1 across the 6 of their papers we have counts for
4 papers · 1 filter
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…