Next: Mathematical Foundation of Up: Department of Computer Previous: Department of Computer

# Foundation of Computer Science Laboratory

/ 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;
• Machine learning;
• Dynamical systems in discrete mathematics; and
• Formal Languages.
The recent impressive advances in VLSI and fiber optics technologies have made it possible to design and build high-performance parallel computers and computer networks. Research in parallel computation has become one of the most important areas in computer science and is accelerating at a rapid pace. We have been working in several principle areas of parallel computation such as, node fault tolerant routing in interconnection networks, sorting and routing in meshes, and so 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. The works in formal language theory focus on homomorphic characterization, Dyck reduction, 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.

The members of this laboratory give lectures in discrete mathematics, geometry, algorithms and data structures, programming languages, language processing systems, and guide student extracurricular projects (SCCP). Currently, there are four SCCP projects in this laboratory:

• The Route Guidance System---An Introduction to Graph Theory and Its Applications, supervised by Prof. Okawa.

The graph theory provides good examples to make student understand how abstract theories work well in resolving practical problems. We study the graph theory through considering problems we meet in constructing a route guidance system.

• Concrete Mathematics, supervised by Prof. Yukita.

The project aims at developing students' skills in experimental mathematics making full use of computers. With these skills, we will investigate unsolved mathematical problems. We also reformulate theoretically solved problems in algorithmic manner. In other words, we "implement" the solutions to the already solved problems.

• PC-UNIX and Networking, supervised by Prof. Yukita.

The project begins with the installation of UNIX on PC's. We experiment various network configurations, through which we gain deep understandings of how network protocols work.

• Parallel Algorithms and Data Structures, supervised by Prof. Gu.

In this project, we have a comprehensive study in algorithms and data structures based on both sequential and parallel computation models.

Developing coursewares is another important teaching activity of this laboratory. Coursewares have been developed in the areas, Vector Calculus, Fourier Analysis and Mathematics for CG. All of them feature top-down approaches and self-learning by computers. In the middle/long term plan, we will develop more coursewares in parallel computation, machine learning, discrete mathematics, and so on, based on our research works.

Refereed Journal Papers

1. S. Hirose and S. Okawa. Dyck reductions of minimal linear languages yield the full class of recursively enumerable languages. IEICE Trans. on Information and Systems, E79-D(2):161--164, 1996.

We give a direct proof of the result of Latteux and Turakainen that the full class of recursively enumerable languages can be obtained from minimal linear languages (which are generated by linear context-free grammars with only one nonterminal symbol) by Dyck reductions (which reduce pairs of parentheses to the empty word).

2. Qian-Ping Gu, Satoshi Okawa, and Shietung Peng. Set-to-set fault tolerant routing in hypercubes. IEICE Trans. on Fundamentals, E79-A:483--488, 1996.

In this paper, we give an algorithm which, given a set $F$ of at most $n-k$ faulty nodes, and two sets $S=\{s_1,\ldots,s_k\}$ and $T=\{t_1,\ldots,t_k\}$, $1\leq k\leq n$, of non-faulty nodes in $n$-dimensional hypercubes $H_n$, finds $k$ fault-free node disjoint paths $s_i\rightarrow t_{j_i}$, where $(j_1,\ldots,j_k)$ is a permutation of $(1,\ldots,k)$, of length at most $n+k$ in $O(kn\log k)$ time. The result of this paper implies that $n$ disjoint paths of length at most $2n$ for set-to-set node disjoint path problem in $H_n$ can be found in $O(n^2\log n)$ time.

3. Qian-Ping Gu and Shietung Peng. An efficient algorithm for node-to-node routing in hypercubes with faulty clusters. The Computer Journal, 39:14--19, 1996.

In this paper, we study node-to-node fault tolerant routing problem in $n$-dimensional hypercubes $H_n$ based on the cluster fault tolerant model. For a graph $G$, a fault cluster is a connected subgraph of $G$ such that all its nodes are faulty. In cluster fault tolerant routing problems, how many fault clusters and how large of those clusters can be tolerated are studied. It was proved that for node-to-node routing, $H_n$ can tolerate as many as $n-1$ fault clusters of diameter at most 1 with at most $2n-3$ fault nodes in total. In this paper, we give an algorithm which, given at most $n-1$ fault clusters of diameter at most 1 with $2n-3$ fault nodes in total and non-fault nodes $s$ and $t$ in $H_n$, finds a fault-free path $s\rightarrow t$ of length at most $n+2$ in $O(n)$ time. The upper bounds on the time complexity of the algorithm and the length of the fault-free path in this paper are optimal.

4. Jun Gu, Qian-Ping Gu, and Dingzhu Du. Convergence Properties of Optimization Algorithms for the SAT Problem. IEEE Trans. on Computers, 45(2):209--219, 1996.

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 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. Many optimization techniques, such as the steepest descent method, Newton's method, and the coordinate descent method, can be used to solve the {\it Universal SAT} problem. In this paper, we prove that, %subject to certain conditions, when the initial solution is sufficiently close to the optimal solution, 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 steepest 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 satisfiable $CNF$ Boolean formulas.

5. Qian-Ping Gu and Shietung Peng. Node-to-node cluster fault tolerant routing in star graphs. Information Processing Letters, 56:29--35, 1995.

This paper defines a new fault tolerant routing model, {\em cluster fault tolerant routing}, and gives the solutions for node-to-node cluster fault tolerant routing in star graphs.

6. Qian-Ping Gu and Shietung Peng. Linear time algorithms for fault tolerant routing in hypercubes and star graphs. IEICE Trans. on Information and Systems, E78-D:1171--1177, 1995.

In this paper, we study the following node-to-node fault tolerant routing problem: In the presence of up to $n-1$ faulty nodes, find a fault-free path which connects any two non-faulty nodes $s$ and $t$ in an $n$-connected graph. For node-to-node fault tolerant routing in $n$-dimensional hypercubes $H_n$, we give an algorithm which finds a fault-free path $s\rightarrow t$ of length at most $d(s,t)+2\lceil\log \frac{n}{d(s,t)}\rceil$ in $O(n)$ time, where $d(s,t)$ is the distance between $s$ and $t$. We also show that a fault-free path $s\rightarrow t$ in $H_n$ of length at most $d(s,t)+2i$, $1\leq i< \lceil\log \frac{n}{d(s,t)}\rceil$, can be found in $O(d(s,t)\frac{n}{2^{i-1}}+n)$ time. For node-to-node fault tolerant routing in $n$-dimensional star graphs $G_n$, we give an algorithm which finds a fault-free path $s\rightarrow t$ of length at most $\min\{d(G_n)+3,d(s,t)+6\}$ in $O(n)$ time, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$. It is previously known that, in $H_n$, a fault-free path $s\rightarrow t$ of length at most $d(s,t)$ for $d(s,t)=n$ and at most $d(s,t)+2$ for $d(s,t)< n$ can be found in $O(d(s,t)n)$ time, and in $G_n$, a fault-free path $s\rightarrow t$ of length at most $\min\{d(G_n)+1,d(s,t)+4\}$ can be found in $O(d(s,t)n)$ time. When the time efficiency of finding the routing path is more important than the length of the path, the algorithms in this paper are better than the previous ones.

7. Qian-Ping Gu and Shietung Peng. Fault tolerant routing in toroidal networks. IEICE Trans. on Information and Systems, to appear, 1996.

In this paper, we study the following node-to-node and node-to-set routing problems in $r$-dimensional torus $T^r_n$ with $r\geq 2$ and $n\geq 4$ nodes in each dimension: given at most $2r-1$ faulty nodes and non-faulty nodes $s$ and $t$ in $T^r_n$, find a fault-free path $s\rightarrow t$; and given at most $2r-k$ faulty nodes and non-faulty nodes $s$ and $t_1,\ldots,t_k$ in $T^r_n$, find $k$ fault-free node-disjoint paths $s\rightarrow t_i$, $1\leq i\leq k$. We give an $O(r^2)$ time algorithm which finds a fault-free path $s\rightarrow t$ of length at most $d(T^r_n)+1$ for the node-to-node routing, where $d(T^r_n)$ is the diameter of $T^r_n$. For node-to-set routing, we show an $O(r^3)$ time algorithm which finds $k$ fault-free node-disjoint paths $s\rightarrow t_i$, $1\leq i\leq k$, of length at most $d(T^r_n)+1$. The upper bounds on the length of the found paths are optimal. From this, Rabin diameter of $T^r_n$ is $d(T^r_n)+1$.

8. Qian-Ping Gu and Tadao Takaoka. A parallel algorithm for the longest path problem on acyclic graphs with integer arc lengths. The Trans. of Information Processing Society of Japan, accepted, 1996.

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.

9. Qian-Ping Gu and Shietung Peng. Set-to-set fault tolerant routing in star graphs. IEICE Trans. on Information and Systems, E79-D:282--289, 1996.

In this paper, we give an algorithm which, given a set $F$ of at most $(n-1)-k$ faulty nodes, and two sets $S=\{s_1,\ldots,s_k\}$ and $T=\{t_1,\ldots,t_k\}$, $1\leq k\leq n-1$, of non-faulty nodes in $n$-dimensional star graphs $G_n$, finds $k$ fault-free node disjoint paths $s_i\rightarrow t_{j_i}$, where $(j_1,\ldots,j_k)$ is any permutation of $(1,\ldots,k)$, of length at most $d(G_n)+5$ in $O(kn)$ optimal time, where $d(G_n)=\lfloor \frac{3(n-1)}{2} \rfloor$ is the diameter of $G_n$.

10. S. Yukita. Tessellation automata on free groups. Hiroshima Mathematical Journal, 25(3):561--570, 1995.

Cellular automata on free groups are investigated. Free groups are considered to be the simplest class of examples that model hyperbolic spaces. Two notions of {\em periodicity} and stable periodicityare introduced. With these notions the relations among Period preservability, injectivity and surjectivity of parallel maps are shown to be almost the same as in the case of Euclidean tessellations. We also show the equivalence of Finite orderedness and strong Poisson stability.

Refereed Proceeding Papers

1. Qian-Ping Gu and Shietung Peng. Node-to-node cluster fault tolerant routing in star networks. In Proc. of 1995 Joint Symposium on Parallel Processing (JSPP'95), June 1995.

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$.

2. Qian-Ping Gu and Shietung Peng. Node-to-set routing with optimal path length in star graphs. In Proc. of International Conference on Parallel and Distributed Computing, September 1995.

Given a node $s$ and a set $T=\{t_1,\ldots,t_k\}$ of $k$ nodes in a $k$-connected graph $G$, node-to-set routing is to find $k$ node disjoint paths $P_i: s\rightarrow t_i,~1 \leq i \leq k$. In this paper, we give $O(n^2)$ time algorithms for node-to-set routing in $n$-dimensional star graphs $G_n$ which is $(n-1)$-connected. Our algorithms find $n-1$ node disjoint paths of length at most $d(G_n)+1$ for $n\neq 4,6$ and at most $d(G_n)+2$, otherwise, for node-to-set routing in $G_n$, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$. The optimal upper bound on the length of $k$ disjoint paths for node-to-set routing in a $k$-connected graph $G$ is known as {\it Rabin diameter} of $G$. In this paper, we also prove that Rabin diameter of $G_n$ is $d(G_n)+1$ for $n\neq 4,6$ and $d(G_n)+2$, otherwise.

3. Qian-Ping Gu and Shietung Peng. Finding a routing path of optimal length in hypercubes with fault clusters. In Proc. of the 7th IASTED International Conference on Parallel and Distributed Computing and Systems, October 1995.

In this paper, we give a linear time algorithm which finds a fault-free routing path of optimal length for node-to-node cluster fault tolerant routing in hypercubes. In cluster fault tolerant routing, the routing problem in a graph $G$ is considered under the situation that a certain number of subgraphs of $G$ failed. A cluster is a connected subgraph of $G$ and a cluster is faulty if all nodes in it are faulty. It was proved that for node-to-node routing, an $n$-dimensional hypercube $H_n$ can tolerate as many as $n-1$ fault clusters of diameter at most 1 with at most $2n-3$ fault nodes in total. Given a tolerable set of fault clusters and two distinct non-fault nodes $s$ and $t$ in $H_n$, it was proved that the optimal upper bound of the length of a fault-free path connecting $s$ and $t$ is $n+2$ and the fault-free path of length at most $n+2$ can be found in $O(n^2)$ time. In this paper, we present an $O(n)$ time algorithm which finds a fault-free path of length at most $n+2$ that connects $s$ and $t$.

4. Qian-Ping Gu and Shietung Peng. An efficient algorithm for $k$-pairwise node-disjoint paths problem in hypercubes. In Proc. of the 7th IEEE Symposium on Parallel and Distributed Processing (SPDP'95),IEEE Computer Society, October 1995.

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$.

5. Qian-Ping Gu and Hisao Tamaki. Routing a permutation in the hypercube by two sets of edge-disjoint paths. In Proc. of the 10th International Parallel Processing Symposium (IPPS'96),IEEE Computer Society, 1996.

Consider a hypercube regarded as a directed graph, with one edge in each direction between each pair of adjacent nodes. We show that any permutation on the hypercube can be partitioned into two partial permutations of the same size so that each of them can be routed by edge-disjoint directed paths. This result implies that the hypercube can be made rearrangeable by virtually duplicating each edge through time-sharing (or through the use of two wavelengths in the case of optical connection), rather than by physically adding edges as in previous approaches. When our goal is to route as many source-destination pairs of the given permutation as possible by edge-disjoint paths, our result gives a 2-approximate solution which improves previous ones.

6. Qian-Ping Gu and Shietung Peng. $k$-pairwise cluster fault tolerant routing in star graphs. In Proc. of the 11th International Conference of Systems Engineering (ICSE'96), 1996.

Recently, cluster fault tolerant (abbreviated as CFT in what follows) routing model which is a natural extension of the well studied node fault tolerant routing was introduced. 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 CFT routing, the number of fault clusters and the size of the fault clusters that can be tolerated are studied. In this paper, we study the following $k$-pairwise CFT routing problem in $n$-dimensional star graphs $G_n$: Given a set ${\bf F}$ of fault clusters and $k$ pairs of $2k$ distinct non-fault nodes $(s_1,t_1),\ldots,(s_k,t_k)$ in $G_n$, find $k$ fault-free node disjoint paths that pairwisely connect, one path for one pair, the $k$ node pairs. We show in this paper that for $1\leq k\leq \lceil\frac{n-1}{2}\rceil$, $G_n$ can tolerate as many as $n-2k$ fault clusters of diameter at most 2. A cluster of diameter 2 in $G_n$ has as many as $n$ nodes. The result of this paper shows that for $k$-pairwise CFT routing, star graphs $G_n$ can tolerate as many as $n(n-2k)$ fault nodes under certain conditions. We also give $O(n^2)$ optimal time algorithms which, given a tolerable set ${\bf F}$, find $k$ fault-free node disjoint paths of length at most $d(G_n)+8$ for $k$-pairwise CFT routing problem in $G_n$, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$.

7. Qian-Ping Gu and Shietung Peng. Finding $d$-separated paths in hypercubes. In Proc. of the 11th International Conference of Systems Engineering (ICSE'96), 1996.

Two paths $P$ and $Q$ in a graph $G$ are $d$-separated if for any node $u$ in $P$ and any node $v$ in $Q$ except possibly the common end-nodes, the distance between $u$ and $v$ is at least $d$. In this paper, we study the following node-to-node routing problem in hypercubes: (1) finding 2-separated paths in free space (without obstacles); (2) finding disjoint paths with path-shaped obstacles. We give algorithms to construct the 2-separated/disjoint paths for node-to-node routing problems (1) and (2), and show that the numbers of paths constructed by our algorithms are maximum in the worst case.

8. Qian-Ping Gu and Shietung Peng. Set-to-set disjoint paths in hypercubes. In Proc. of 1996 International Conference on Parallel and Distributed Systems (ICPAD'96), IEEE Computer Society, 1996.

Set-to-set node-disjoint paths problem is that given two sets $S=\{s_1,\ldots,s_k\}$ and $T=\{t_1,\ldots,t_k\}$ of nodes in a graph, find $k$ node disjoint paths $s_i\rightarrow t_{j_i}$, where $(j_1,\ldots,j_k)$ is any permutation of $(1,\ldots,k)$. For general undirect graphs $G(V,E)$, this problem is usually solved by applying flow techniques which take Poly($|V|$) time. In this paper, we give an algorithm which, given $S=\{s_1,\ldots,s_k\}$ and $T=\{t_1,\ldots,t_k\}$, $1\leq k\leq n$, in an $n$-dimensional hypercube $H_n$ which has $2^n$ nodes, finds the $k$ disjoint paths $s_i\rightarrow t_{j_i}$ of length at most $n+\log k+2$ in $O(kn\log^* k)$ time. The previous results of the length of the $k$ paths and the run time of finding the $k$ paths in $H_n$ are $n+k$ and $O(kn\log k)$, respectively.

9. Qian-Ping Gu and Shietung Peng. Optimal algorithms for node fault tolerant routing in hypercubes. In Proc. of 1996 Joint Symposium on Parallel Processing (JSPP'96), 1996.

In this paper, we give an algorithm which, given at most $n-1$ arbitrary faulty nodes and non-faulty nodes $s$ and $t$ in the $n$-dimensional hypercube $H_n$, finds a fault-free path $s\rightarrow t$ of length at most $d(s,t)+2$ for $d(s,t) < n$ and of length $d(s,t)$ for $d(s,t)=n$ in $O(n)$ time, where $d(s,t)$ is the distance between $s$ and $t$. The previous results on the above problem are that (1) Path length: $d(s,t)+2$ for $d(s,t)< n$ and $d(s,t)$ for $d(s,t)=n$. The time complexity: $O(n\log n)$. (2) Path length: $d(s,t)+2\lceil\log\frac{n}{d(s,t)}\rceil$. The time complexity: $O(n)$.\\ We also give an algorithm which, given at most $n-1$ faulty clusters of diameter at most 1 with $2n-3$ faulty nodes in total and non-faulty nodes $s$ and $t$ in $H_n$, finds a fault-free path $s\rightarrow t$ of length at most $d(s,t)+4$ in $O(n)$ time, where a faulty cluster is a connected subgraph of $H_n$ such that all its nodes are faulty. The upper bounds on the length of the path and the time complexity obtained in this paper are optimal.

10. Qian-Ping Gu and Shietung Peng. $d$-separated paths in hypercubes and star graphs. In Proc. of the 2nd IEEE International Conference on Algorithms and Architectures for Parallel Processing (ICA$^3$PP'93), IEEE Computer Society, 1996.

In this paper, we consider a generalized node-disjoint paths problem: $d$-separated paths problem. In a graph $G$, given two distinct nodes $s$ and $t$, two paths $P$ and $Q$, connecting $s$ and $t$, are $d$-separated if $d_{G-\{s,t\}}(u,v)\geq d$ for any $u\in P-\{s,t\}$ and $v\in Q-\{s,t\}$, where $d_{G-\{s,t\}}(u,v)$ is the distance between $u$ and $v$ in the reduced graph $G-\{s,t\}$. $d$-separated paths problem is to find as many $d$-separated paths between $s$ and $t$ as possible. When $d=1$, $d$-separated paths problem becomes conventional node-to-node disjoint paths problem. In this paper, we give the following results on $d$-separated paths problems on $n$-dimensional hypercubes and star graphs $H_n$ and $G_n$. Given $s$ and $t$ in $H_n$, there are at least $(n-2)$ 2-separated paths between $s$ and $t$. $(n-2)$ is the maximum number of $2$-separated paths between $s$ and $t$ for $d(s,t)\geq 4$. Moreover, $(n-2)$ 2-separated paths of length at most $\min\{d(s,t)+2$, $n+1\}$ for $d(s,t)< n$ and of length $n$ for $d(s,t)=n$ between $s$ and $t$ can be constructed in $O(n^2)$ optimal time. For $d\geq 3$, $d$-separated paths in $H_n$ do not exist. Given $s$ and $t$ in $G_n$, there exist exactly $(n-1)$ 3-separated paths between $s$ and $t$. For $1\leq d\leq 3$, $(n-1)$ is the maximum number of $d$-separated paths between $s$ and $t$ in $G_n$. $(n-1)$ 3-separated paths of length at most $\min\{d(s,t)+4, d(G_n)+2\}$ between $s$ and $t$ can also be constructed in $O(n^2)$ optimal time, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$. For $d\geq 5$, $d$-separated paths in $G_n$ do not exist.

Technical Reports

1. Qian-Ping Gu and Shietung Peng. k-pairwise cluster fault tolerant routing in star graphs. Technical Report, 95-1-002, February 21, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

2. Shuichi Yukita. Functional presentation of fourier series convergence. Technical Report, 95-1-011, March 22, 16pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

1. Satoshi Okawa, IEICE, 1995.

Reviewer of IEICE Transactions.

2. Satoshi Okawa, IJFCS, 1995.

Reviewer of IJFCS.

3. Qian Ping Gu, 1995.

Program committee member of the 8th International Conference on Parallel and Distributed Computing and Systems.

4. Qian Ping Gu, 1995.

Program committee member of the 2nd Aizu International Symposium on Parallel Algorithms/Architectures.

5. Qian Ping Gu, 1995.

Session chair of the 1996 International Conference on Parallel and Distributed Systems.

Next: Mathematical Foundation of Up: Department of Computer Previous: Department of Computer

www@u-aizu.ac.jp
October 1996