System Information Sciences

Algorithm Theory B04

  • Prof. Xiao Zhou
  • Assoc. Prof. Takehiro Ito
  • Assis. Prof. Akira Suzuki
KeywordsAlgorithm, Circuit Complexity, Graph Theory

Developments and Applications of Algorithms

Algorithms now play a very important role for the reliability and efficiency in several social systems. We study and develop new algorithmic techniques from the viewpoint of theoretical computer science. In particular, we deal with several problems related to “graphs” and “combinatorial reconfiguration.”

  1. A graph consists of a set of vertices and a set of edges, each of which joins a pair of vertices. Graphs can be used to model many practical problems: For example, the server supply-assignment problem for computer networks (see Fig.1) and the scheduling problem can be formulated as the graph flow and coloring problems, respectively.
  2. In combinatorial reconfiguration, we are asked to transform the current configuration into a desired one by step by step operations. The 15-puzzle is one of such problems (see Fig.2), and there are many applications such as changing frequency assignments, monitoring systems, and so on.

Students in our laboratory can select research topics according to their own interests. We study algorithms from the theoretical viewpoint, but we sometimes implement developed algorithms to evaluate them from the practical viewpoint.

  • Modeling the server supply-assignment problem for computer networks

  • An example of 15-puzzle