Next: Mathematical Foundation of
Up: Department of Computer
Previous: Department of Computer
/ 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.
- Algorithms and computational complexity;
- Programming languages; and
- Discrete Mathematics.
The research in this laboratory is divided into
two parts.
The first part consists of the work that
follows the research in the above areas.
The goal of this research is to provide
the theoretical foundations for the education and research
activities in this university.
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
- Parallel computation;
-
Computational learning theory; and
-
Dynamical systems in discrete mathematics.
In one principle area of parallel computation,
node fault tolerant routing
in interconnection networks,
this laboratory has been obtaining
some of the most top level results in the world.
Many creative works in other areas of parallel computation,
computational learning theory, and
dynamical systems in discrete mathematics
have also been obtained.
Many of our results have been
published/accepted by leading international journals
and conferences.
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
-
Q. Gu and J. Gu.
Algorithms and average time bounds of sorting on a mesh connected
computer.
IEEE Trans. on Parallel and Distributed Systems, 5(3):308-315,
March 1994.
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.
-
Q. Gu and J. Gu.
Two packet routing algorithms on a mesh connected computer.
IEEE Trans. on Parallel and Distributed Systems, accepted in
June, 1993,
1993.
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
-
Q. Gu, S. Okawa, and S Peng.
Disjoint path in hypercubes and star graphs.
In Joint Symposium on Parallel Processing 1994, pages 49-56,
1994.
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.
-
Q. Gu and S. Peng.
Efficient algorithms for disjoint paths on star networks.
In The 6th Transputer/Occam International Conference, pages
accepted in January, 1994,
1994.
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.
-
Q. Gu and T. Takaoka.
A parallel algorithm for the longest path problem on acyclic graphs
with integer arc lengths.
In The 6th Transputer/Occam International Conference, pages
accepted in January, 1994,
1994.
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.
Books
-
Shuuichi Yukita.
UNIX BLUE BOOK - software factory (in Japanese).
Super Learning System. McGraw-Hill, Tokyo,
1993.
Technical Reports
-
Q. Gu and T. Takaoka.
A parallel algorithm for the longest path problem of acyclic graphs.
TR 93-1-002, The University of Aizu, Department of Computer
Software, The University of Aizu, Aizu-Wakamatsu, Fukushima, Japan 965-80,
September 1993.
-
Q. Gu and S. Peng.
Efficient algorithms for disjoint paths in star graphs.
TR 93-1-015, The University of Aizu, Department of Computer
Software, The University of Aizu, Aizu-Wakamatsu, Fukushima, Japan 965-80,
November 1993.
-
S. Peng, Q. Gu, and S. Okawa.
Set-to-set routing in hypercubes and star graphs.
TR 94-1-002, The University of Aizu, Department of Computer
Software, The University of Aizu, Aizu-Wakamatsu, Fukushima, Japan 965-80,
February 1994.
-
Q. Gu and S. Peng.
Disjoint path paradigms in incomplete star networks.
TR 94-1-003, The University of Aizu, Department of Computer
Software, The University of Aizu, Aizu-Wakamatsu, Fukushima, Japan 965-80,
February 1994.
Academic Activities
-
Satoshi Okawa,
March- 1993.
Reviewer of The Institute of
Electronics,INformation and Communication Engineers (IEICE).
Next: Mathematical Foundation of
Up: Department of Computer
Previous: Department of Computer