/ 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
Machine learning is another major area that we are interested in. Our focuses are on computational learning theory and its relationship with empirical machine learning conducted in the field of artificial intelligence. The works in dynamical systems in discrete mathematics include Tessellation automata theory, algebra structures of interconnection networks, and so on. Many of our works have been published/accepted by leading international journals and conferences.
The research activities in this laboratory are based on the free work of each faulty member. Faculty members exchange their ideas and results through regular seminars and free discussions to work on common global areas.
Several leading experts in the world were invited to give talks in several areas of computer science last year. These talks have greatly stimulated and brought fresh air to the work here. Joint researchs with other laboratories and other universities/institutions have been actively conducted as well. This laboratory gave many contributions to the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis (pAs'95).
The members of this laboratory give lectures in discrete mathematics, geometry, algorithms and data structures, programming languages, and guide student extracurricular projects (SCCP). Currently, there are four SCCP projects in this laboratory:
Refereed Journal Papers
The satisfiability (SAT) problem is a basic problem in computing theory. Presently, an active area of research on SAT problem is to design efficient algorithms for verifying the satisfiability of a {\it CNF} Boolean formula, i.e., finding a solution for a satisfiable {\it CNF} formula. A new formulation, the {\it Universal SAT} problem model, which transforms the SAT problem on Boolean space into an optimization problem on real space has been developed. In this paper, we prove the convergence ratios of three basic optimization methods for the {\it Universal SAT} problem. We show that, subject to certain conditions, the steepest descent method has a linear convergence ratio $\beta<1$, Newton's method has a convergence ratio of order two, and the convergence ratio of the coordinate descent method is approximately $(1-\beta/m)$ for the {\it Universal SAT} problem with $m$ variables. An algorithm based on the coordinate descent method for the {\it Universal SAT} problem is also presented in this paper. Experimental results show that this algorithm is more efficient than the previous ones in finding a solution for certain classes of $CNF$ Boolean formulae.
In this paper, we give two algorithms for the 1-1 routing problems on a mesh-connected computer. The first algorithm, with queue size 28, solves the 1-1 routing problem on an $n\times n$ mesh-connected computer in $2n+O(1)$ steps. This improves the previous queue size $75$. The second algorithm solves the 1-1 routing problem in $2n-2$ steps with queue size $12t_s/s$, where $t_s$ is the time for sorting an $s\times s$ mesh into a row major order for all $s\geq 1$. This result improves the previous queue size $18.67t_s/s$.
Refereed Proceeding Papers
In this paper, we study node-to-node fault tolerant routing problem in $n$-dimensional star graphs $G_n$ based on the cluster fault tolerant model which is a natural extension of the well studied node fault tolerant model. For a graph $G$, a cluster $C$ is a connected subgraph of $G$, and $C$ is called fault cluster if all nodes in $C$ are faulty. In cluster fault tolerant routing, the number of fault clusters and the size of the fault clusters that can be tolerated are studied. For node-to-node fault tolerant routing problem in $G_n$, we prove that $G_n$ can tolerate as many as $n-2$ arbitrary fault clusters of diameter at most 2. This result shows that star graphs $G_n$ can tolerate as many as $n(n-2)\approx (\log N/\log\log N)^2$ fault nodes, where $N=n!$ is the number of nodes in $G_n$, if the fault nodes can be partitioned into clusters. We also give an $O(n^2)$ optimal time algorithm which finds a fault-free routing path of length at most $d(G_n)+7$ for node-to-node cluster fault tolerant routing problem in $G_n$, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$.
In this paper, we give an $O(r^2)$ time algorithm for constructing a fault-free routing path of optimal length between any two non-fault nodes of a $r$-dimensional torus with $2r-1$ faulty nodes. %The fastest previously known algorithm for this problem takes $O(r^3)$ time; We show that Rabin diameter of a $r$-dimensional torus is its diameter plus one. We also describe a cluster fault tolerant (CFT) routing model and give an efficient algorithm for node-to-node CFT routing.
We give efficient algorithms for node disjoint path problems in incomplete star graphs which are defined in this paper to reduce the large gaps in the size of systems based on star graph topologies. Four disjoint path paradigms in incomplete star graphs are discussed: (1) disjoint paths between a pair of nodes $s$ and $t$, (2) disjoint paths from a node $s$ to a set $T$ of nodes, (3) disjoint paths from a set $S$ of nodes to a set $T$ of nodes, and (4) disjoint paths between node pairs $(s_i,t_i)$. We give algorithms which can find the maximum number of disjoint paths for these paradigms in optimal time. For an $n$-dimensional incomplete star graph $G_{n,m}$, the length of the disjoint paths constructed by our algorithms is at most $d(G_{n,m})+c$, where $d(G_{n,m})$ is the diameter of $G_{n,m}$ and $c$ is a small constant. This paper also shows that wide-diameter $d^W_{n-2}(G_{n,m})$, Rabin-diameter $d^R_{n-2}(G_{n,m})$, set-diameter $d^S_{n-2}(G_{n,m})$, and pair-diameter $d^P_{\lceil\frac{n-2}{2}\rceil}(G_{n,m})$ of $G_{n,m}$ are at most $d(G_{n,m})+c$.
In this paper, we study the fault tolerant
properties of $n$-dimensional hypercubes $H_n$
for node-to-set and set-to-set routing problems
on a new model,
In this paper, we introduce a general
fault-tolerant routing problem,
The satisfiability (SAT) problem
is a basic problem in computing theory and artificial intelligence.
In this paper,
we describe and analyze the average time complexity
of a local search algorithm, the $SAT1.2$ algorithm,
for the SAT problem.
For the randomly generated $CNF$ formulae with
$n$ clauses, $m$ variables, and $l$ literals
in each clause,
the average run time of the $SAT1.2$ algorithm
is $O(m^{O(1)}n^2)$
for $l\geq 3$ and $n/m\leq \alpha 2^l/l$, where
$\alpha
In this paper, we give optimal time algorithms for
the following node disjoint path problems in
$n$-dimensional star graphs $G_n$:
(1) Given an arbitrary node $s$ and a set of arbitrary
distinct nodes $T=\{t_1,\ldots,t_{n-1}\}$, $s\not\in T$,
in $G_n$, find $n-1$ node disjoint paths connecting
$s$ and each node of $T$; and
(2) Given arbitrary $k= \lceil \frac{n-1}{2}\rceil$
pairs of distinct nodes
$(s_1,t_1),\ldots,(s_k,t_k)$ in $G_n$,
find $k$ node disjoint paths, one path connecting
one pair of nodes.
For problem (1), our algorithm finds
the $n-1$ node disjoint paths
of length at most $d(G_n)+4$ in $O(n^2)$ optimal time,
where $d(G_n)=\lfloor\frac{3(n-1)}{2}\rfloor$ is
the diameter of $G_n$.
The length of the paths given in this paper improves
the previous result of $5n-2$.
For problem (2), our algorithm finds the $k$
node disjoint paths of length at most $d(G_n)+5$
in $O(n^2)$ optimal time.
Our results improve the previous ones of
the time $O(n^4\log n)$ and the length $4(n-2)$, respectively.
From the upper bounds on the length of the paths for
problems (1) and (2) of this paper,
we also get that Rabin-diameter $d^R_{n-1}(G_n)$
and $k$-pair-diameter $d^P_{k}(G_n)$
of $G_n$ satisfy $d^R_{n-1}(G_n)\leq d(G_n)+4$
and $d^P_k(G_n)\leq d(G_n)+5$, respectively,
where $k=\lceil\frac{n-1}{2}\rceil$.
This paper presents a parallel algorithm that
computes the single source longest path problem
on acyclic graphs $G(V,A)$ with integer arc lengths
on SIMD-SM-EREW parallel computers.
The algorithm solves the problem in
$O(\log^2(ln))$ time, $O((ln)^{2.376})$ processors,
and $O((ln)^2)$ memory space,
where $n=|V|$ and the arc lengths are
integers in the set $\{1,2,\ldots,l\}$.
For any constant $l$, our algorithm
solves the single source longest path problem
in $O(\log^2n)$ time, $O(n^{2.376})$ processors,
and $O(n^2)$ memory space.
Our algorithm is then
used to derive $O(\log^2n)$ time, $O(n^{2.376})$ processors,
and $O(n^2)$ memory space parallel algorithms for
a number of problems, such as minimum coloring,
maximum clique, and so on, of permutation graphs
on an SIMD-SM-EREW computer.
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 set-to-set routing in $n$-dimensional hypercubes $H_n$
our algorithm finds the routing paths
of length at most $2n$ in $O(n^2\log n)$ time.
For set-to-set routing in $n$ dimensional star graphs $G_n$,
our algorithm finds the routing paths
of length at most $\lfloor \frac{3(n-1)}{2} \rfloor + 5$
in $O(n^2)$ optimal time.
Unrefereed Papers
In this paper, we give an efficient algorithm for the following $k$-pairwise node disjoint path problem in $n$-dimensional hypercubes $H_n$: Given $k=\lceil \frac{n}{2}\rceil$ pairs of $2k$ distinct nodes $(s_1,t_1),\ldots,(s_k,t_k)$ in $H_n$, $n\geq 4$, find $k$ node disjoint paths, each path connecting one pair of nodes. Our algorithm finds the $k$ node disjoint paths in $O(n^2\log^* n)$ time which improves the previous result of $O(n^2\log n)$. The length of the paths constructed in our algorithm is at most $n+\lceil \log n\rceil +1$ which improves the previous result of $2n$ as well. The result of this paper shows that the $k$-pair-diameter %and $k$-set-diameter of $H_n$ satisfy $d^P_{\lceil\frac{n}{2}\rceil}(H_n)$ of $H_n$ satisfies $d^P_{\lceil\frac{n}{2}\rceil}(H_n)\leq n+\lceil\log n\rceil+1$.