Kyushu University Academic Staff Educational and Research Activities Database
Researcher information (To researchers) Need Help? How to update
Yutaro YAMAGUCHI Last modified date:2020.06.30



Graduate School
Undergraduate School


E-Mail *Since the e-mail address is not displayed in Internet Explorer, please use another web browser:Google Chrome, safari.
Homepage
https://kyushu-u.pure.elsevier.com/en/persons/yutaro-yamaguchi
 Reseacher Profiling Tool Kyushu University Pure
http://tcs.inf.kyushu-u.ac.jp/~ymgc/
Academic Degree
Ph.D. in the field of Mathematical Informatics (from University of Tokyo)
Field of Specialization
Combinatorial Optimization, Discrete Mathematics (Graphs, Matroids, Submodular Functions, etc.), Algorithms, Operations Research, Game Theory
Total Priod of education and research career in the foreign country
00years04months
Research
Research Interests
  • Combinatorial Optimization on Group-Labeled Graphs
    keyword : Group-labeled graphs, Algorithms, Matroids, Matchings, Paths
    2011.07.
  • Discrete Mathematics in Combinatorial Optimization
    keyword : Graphs (Networks), Matroids, Submodular Functions
    2013.01.
  • Stochastic Combinatorial Optimization with Queries
    keyword : Stochastic Optimizations, Queries, Matchings, Linear Programming, Submodular Optimization
    2017.04.
Academic Activities
Papers
1. Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi, Finding a Path in Group-Labeled Graphs with Two Labels Forbidden, Journal of Combintorial Theory, Series B, 143, 65-122, 2020.07.
2. Takanori Maehara, Yutaro Yamaguchi, Stochastic Packing Integer Programs with Few Queries, Mathematical Programming (Series A), 182, 141-174, 2020.07.
3. Yutaro Yamaguchi, A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs, The 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), 1923-1932, 2020.01, We study a constrained shortest path problem in group-labeled graphs with nonnegative edge length, called the shortest non-zero path problem. Depending on the group in question, this problem includes two types of tractable variants in undirected graphs: one is the parity-constrained shortest path/cycle problem, and the other is computing a shortest noncontractible cycle in surface-embedded graphs.

For the shortest non-zero path problem with respect to finite abelian groups, Kobayashi and Toyooka (2017) proposed a randomized, pseudopolynomial algorithm via permanent computation. For a slightly more general class of groups, Yamaguchi (2016) showed a reduction of the problem to the weighted linear matroid parity problem. In particular, some cases are solved in strongly polynomial time via the reduction with the aid of a deterministic, polynomial algorithm for the weighted linear matroid parity problem developed by Iwata and Kobayashi (2017), which generalizes a well-known fact that the parity-constrained shortest path problem is solved via weighted matching.

In this paper, as the first general solution independent of the group, we present a rather simple, deterministic, and strongly polynomial algorithm for the shortest non-zero path problem. The algorithm is based on Dijkstra's algorithm for the unconstrained shortest path problem and Edmonds' blossom shrinking technique in matching algorithms, and clarifies a common tractable feature behind the parity and topological constraints in the shortest path/cycle problem..
4. Yutaro Yamaguchi, Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity, SIAM Journal on Discrete Mathematics, 30, 1, 474-492, 2016.03.
Membership in Academic Society
  • The Japan Society for Industrial and Applied Mathematics
  • The Operations Research Society of Japan