Pioneering research of efficient discrete algorithms


(1) A theory of linear time algorithms
Many graphs representing the structure such as the internet connection can be characterized by a generalized form of trees, called tree-width. For such graphs with small tree-width, many combinatorial problems can be efficiently solved. The beginning this research field was developed from the paper "Linear-time computability of combinatorial problems on series-parallel graphs"which was published in JACM and cited more than 100 times. This paper has given a unified design theory of linear time algorithm for a number of combinatorial problems on graphs obtained by repeating the series connection and parallel connection. The impact of this theory given in the field of linear-time algorithm is very large.

(2) Discrete efficient algorithms
As one big performance, more efficient deployment of theory and algorithms on planar graphs in particular may be mentioned. They have given efficient algorithms for embedding planar graphs, coloring problem, Hamiltonian cycle problem, independent set proglem, multiple flow problem, etc. Many of them can be done in linear time. These efficiency and design methods inspired by an entirely new theory has been introduced. The number of papers related to the results of planar graph theory and algorithms is more than 100. Such papers are published in SIAM J. Computing, IEEE Trans. CAD, STOC, ICALP, etc. The English book "Planar Graphs: Theory and Algorithms" (North-Holland) summarizes these results.

Related Researches

Category

Communication
(Engineering Sciences for Electronics, Information and Communication Engineers)

Events in World

no data.
Page Top