- Home
- Programs & Courses
- Graduate School of Science and Engineering : Science of Environment and Mathematical Modeling (Laboratories : Discrete Mathematics Laboratory)

## Graduate School of Science and Engineering

Science of Environment and Mathematical Modeling

### Discrete Mathematics Laboratory

#### Staff

Yoshihide WATANABE

[Professor]

Acceptable course | |
---|---|

Master's degree course | ○ |

Doctoral degree course | ○ |

yowatana@mail.doshisha.ac.jp

Office : YE-218

Database of Researchers

#### Research Topics

<1> Min-Plus (Tropical ) Linear Algebra and Combinatorial Optimization Problems from the view point

of Tropical Geometry

<2> Mathematical Aspects of Various Kinds of Network Optimization Problems on Graphs

<3> Polynomial Representation of Cellular Automata and its Application to Stability Analysis

of Tropical Geometry

<2> Mathematical Aspects of Various Kinds of Network Optimization Problems on Graphs

<3> Polynomial Representation of Cellular Automata and its Application to Stability Analysis

#### Research Contents

Min-Plus algebra is the algebra (semi-ring) with two kinds of operations “Min” and “Plus”. It has the origin in the shortest path problem on graphs and often arises in the description of the algorithms of network optimization problems. Then, we have to analyze the Min-Plus linear equations in order to get the algorithm for solving combinatorial optimization problems. However, it is not easy because the “Min” operation does not have the inverse. Tropical Geometry is the algebraic geometry on Min-Plus (Tropical) Algebra and treat with piecewise linear figures. In Tropical Geometry, tropical variety as the solution of tropical equations is defined in a wide sense and such extended solutions may give innovative viewpoints in the analysis of tropical equations arising in various kinds of combinatorial optimization problems. So, we investigate algorithms for combinatorial optimization problems, especially for network optimization problems, from the viewpoint of tropical geometry. We express the local transition functions of cellular automata by polynomial functions; by using such expression we can classify Cellular Automata under some group action, specify the class of cellular automata admitting the various kinds of conservation laws. We are going to analyze the stability of some kind of cellular automata appearing in the analysis of traffic model such as SlS model. Such investigation serves to clarify the validity of using cellular automata in the elucidation of traffic jam.

#### Keywords

- Min-Plus Linear Algebra
- Tropical Geometry
- Combinatorial Optimization Problem
- Network Optimization Problem
- Graph

- Cellular Automata
- Polynomial Expression
- Conservation Laws
- Stability Analysis