/ Satoshi Okawa / Professor
/ Qian Ping Gu / Associate Professor
/ Shuichi Yukita / Associate Professor
The research and education activities in this laboratory focus on the theoretical foundations of computers and computations. In particular, our work covers the following areas.
The second part of our work is the creative research in some specific areas of the theoretical foundations of computer science. Currently, we are working on
This laboratory gives lectures in discrete mathematics, geometry, algorithms, and guides students in their extracurricular projects in our creative research. In the middle to long term plan, we will develop courseware in parallel computation, computational learning theory, and dynamical systems in discrete mathematics based on our research results.
The research activities in this laboratory are based on the free work of each faculty member. Faculty members exchange their ideas and results through regular seminars and free discussions to work on common global areas. In the last year, a regular algorithm seminar (once a week) was organized, and eight leading experts in the world were invited to give talks in several areas of computer science. These talks have greatly stimulated and brought fresh air to the work here. The work of this laboratory has also been actively promoted outside the university at domestic and international conferences.
Refereed Journal Papers
In this paper, we give three new parallel sorting algorithms on a mesh connected computer with xbm/wrap around connections (i.e., a torus). These three algorithms, with the minimum queue size of , sort random input data items into a blocked snake-like row major order, a row major order, and a snake-like row major order, in , , and average steps, respectively. These results improve the previous results of , , and , respectively. In addition, we prove in this paper that the distance bound on a torus is an average time lower bound independent of indexing schemes of sorting random data items on it.
In this paper, we give two algorithms for the routing problems on a mesh connected computer. The first algorithm, with a queue size of , solves the problem on an mesh connected computer in steps. This improves the previous result of a queue size . The second algorithm solves the problem in steps with a queue size of , where is the time for sorting an mesh into a row major order for all . This result improves the previous result of a queue size of . Both of our algorithms have important applications in reducing the hardware cost on a mesh connected computer.
Refereed Proceeding Papers
The set-to-set routing which allows certain node failure is considered. We first present an interesting theorem for the set-to-set routing problem in general graphs. Then efficient algorithms are given for the set-to-set routing problem in hypercubes and star graphs. Hypercubes and star graphs have been accepted as attractive interconnection networks. They have logarithmic and sublogarithmic node degree and diameter, respectively. They both possess rich structure and symmetry properties as well as many desirable fault tolerance characteristics, For -dimensional hypercubes and star graphs, our algorithms run in optimal time. The algorithms find the node disjoint paths of length at most for hypercubes and the node disjoint paths of length at most for star graphs.
Star Graphs have recently been accepted as an attractive choice for interconnection networks. They have sublogarithmic node degree and diameter. Like hypercubes, star graphs possess rich structure and symmetry properties as well as many desirable fault tolerance characteristics. This paper presents optimal time algorithms for finding disjoint paths which are the base for fault tolerant computation in a star graph. Our results significantly improve the previous results. For pairwise disjoint path problem, our algorithm is time which improves the previous result of . The length of paths constructed in our algorithm for three variations of disjoint path problems is bounded by the diameter of the star graph plus a small constant which is also an improvement over the previous results.
This paper presents a parallel algorithm that computes the single source longest path problem on acyclic graphs with integer arc lengths on SIMD-SM-EREW parallel computers. The algorithm solves the problem in time, processors, and memory space, where and the arc lengths are integers in the set . For any constant , our algorithm solves the single source longest path problem in time, processors, and memory space. With some modifications, our algorithm solves the single source shortest path problem on a graph with edge lengths drawn from the integer set in time, processors, and memory space. Our algorithm can also be used to derive time, processors, and memory space parallel algorithms for a number of problems, such as minimum coloring, maximum clique, and so on, for permutation graphs on an SIMD-SM-EREW computer.
Reviewer of The Institute of Electronics,INformation and Communication Engineers (IEICE).