/ 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.
Books
Technical Reports
Academic Activities
Reviewer of The Institute of Electronics,INformation and Communication Engineers (IEICE).