Naoki Katoh

Major research fields

NaokiKatohalgorithm, combinatorial optimization, evacuation planning

An algorithm is a procedure for solving problems by computer. Currently, we are enjoying the internet society. It is constructed on the foundation of high-speed computer network and high-performance computers as well as very efficient algorithms. Main interests of the laboratory are developing efficeint algorithms for the problems that occur in real world. In particular, we focus on discrete structures such as road networks, computer networks, protein structures, and buildingstrctures modelled by graphs and networks. A graph consists of a set of vertices and a set of edges, each joining a pair of vertices.

In particular, as concrete problems, we are interesting in evacuation planning problems from Tsunami in coastal areas such as Osaka and Wakayama where we foucs on how people can evacuate to safety places as quickly as possible and where we should locate evacuation buildings. These problems can be modeled by using network flows. The other topic we are interested in in combinatorial rigidity theory that seeks to determine the rigidity of a bar-joint or body-hinge framework which models buildings, proteins and etc. This problem has applications to various fields such as architectural design and the analysis of protein flexibility. Also, we investigate efficient algorithms to solve combinatorial optimization problems related to graphs.

Major relevant publications

  1. Naoyuki Kamiyama, Naoki Katoh: The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths. Discrete Applied Mathematics 178: 89-100 (2014)
  2. Atsushi Takizawa, Masaki Inoue and Naoki Katoh: An Emergency Evacuation Planning Model using the Universally Quickest Flow, The Review of Socionetwork Strategies, 6(1), pp.15-28, Jun. 2012.
  3. Naoki Katoh, Shin-ichi Tanigawa: A Proof of the Molecular Conjecture, Discrete and Computational Geometry, Vol.45 No.4, (2011) 645-700.
  4. A. Takizawa, Y. Miyata and N. Katoh, Enumeration of Floor Plans Based on Zero-Suppressed Binary Decision Diagram, The International Journal of Architectural Computing,Vol. 13, No. 1, pp. 25-44, 2015
  5. Y. Kobayashi, Y. Higashikawa, N. Katoh, and N. Kamiyama, An Inductive Construction of Minimally Rigid Body-Hinge Simple Graphs, Theoretical Computer Science, 556:2-12, 2014.