13 citations · 19 across the 9 of their papers we have counts for
10 papers
A Shortest Augmenting Path Algorithm for Linear Matroid Parity
Kou Hamada, Satoru Iwata
The matroid parity problem serves as a fundamental framework that generalizes both graph matching and matroid intersection. Although the general version is intractable, Lovász (198…
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals
Satoru Iwata, Yu Yokoi
Let be a multigraph with a set of terminals. A path in is called a -path if its ends are distinct vertices in and no internal vertices belong to…
A Weighted Linear Matroid Parity Algorithm
Satoru Iwata, Yusuke Kobayashi
The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential…
Index Reduction for Differential-Algebraic Equations with Mixed Matrices
Satoru Iwata, Taihei Oki, Mizuyo Takamatsu
Differential-algebraic equations (DAEs) are widely used for modeling of dynamical systems. The difficulty in solving numerically a DAE is measured by its differentiation index. For…
Making Bipartite Graphs DM-irreducible
Kristóf Bérczi, Satoru Iwata, Jun Kato +1
The Dulmage--Mendelsohn decomposition (or the DM-decomposition) gives a unique partition of the vertex set of a bipartite graph reflecting the structure of all the maximum matching…
Improved Approximation Algorithms for k-Submodular Function Maximization
Satoru Iwata, Shin-ichi Tanigawa, Yuichi Yoshida
This paper presents a polynomial-time -approximation algorithm for maximizing nonnegative -submodular functions. This improves upon the previous -appr…