Extending the very popular tori interconnection networks[1]-[3], Torus-Connected Cycles (TCC) have been proposed as a novel network topology for massively parallel systems [5]. Here, the set-to-set disjoint paths routing problem in a TCC is solved. In a TCC(k,n), it is proved that paths of lengths at most kn2+2n can be selected in O(kn2) time.

Reducing the number of link crossings in a network drawn on the plane such as a wiring board is a well-known problem, and especially the calculation of the minimum number of such crossings: this is the crossing number problem. It has been shown that finding a general solution to the crossing number problem is NP-hard. So, this problem is addressed for particular classes of graphs and this is also our approach in this paper. More precisely, we focus hereinafter on the torus topology. First, we discuss an upper bound on cr(T(2, k)) the number of crossings in a 2-dimensional k-ary torus T(2, k) where k ≥ 2: the result cr(T(2, k)) ≤ k(k - 2) and the given constructive proof lay foundations for the rest of the paper. Second, we extend this discussion to derive an upper bound on the crossing number of a 3-dimensional k-ary torus: cr(T(3, k)) ≤ 2k4 - k3 - 4k2 - 2⌈k/2⌉⌊k/2⌋(k - (k mod 2)) is obtained. Third, an upper bound on the crossing number of an n-dimensional k-ary torus is derived from the previously established results, with the order of this upper bound additionally established for more clarity: cr(T(n, k)) is O(n2k2n-2) when n ≥ k and O(nk2n-1) otherwise.

The Möbius cube is a variant of the hypercube. Its advantage is that it can connect the same number of nodes as a hypercube but with almost half the diameter of the hypercube. We propose an algorithm to solve the node-to-node disjoint paths problem in n-Möbius cubes in polynomial-order time of n. We provide a proof of correctness of the algorithm and estimate that the time complexity is O(n2) and the maximum path length is 3n-5.

A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm.

In this paper, a new network structure called generalized Hierarchical Completely-Connected networks (HCCs) is proposed, and its properties and features are evaluated. Simple routing strategies for HCCs are also developed for shortest-paths routing algorithms. A set of HCCs constructed by the proposed method includes some conventional hierarchical networks, then it is called generalized one. The construction of an HCC starts from a basic block (a level-1 block) which consists of n nodes of constant degree. Then a level-h block for h 2 is constructed recursively by interconnecting any pair of macro nodes (n level-(h-1) blocks) completely. An HCC has a constant node-degree regardless of an increase in its size (the number of nodes). Furthermore, since an HCC has a hierarchically structured topology and the feature of uniformity, a wide variety of inter-cluster connections is possible. Evaluation results show that an HCC is suitable for very large computer systems.

Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.

A feedback node set (FNS) of a graph is a subset of the nodes of the graph whose deletion makes the residual graph acyclic. By finding an FNS in an interconnection network, we can set a check point at each node in it to avoid a livelock configuration. Hence, to find an FNS is a critical issue to enhance the dependability of a parallel computing system. In this paper, we propose a method to find FNS's in n-pancake graphs and n-burnt pancake graphs. By analyzing the types of cycles proposed in our method, we also give the number of the nodes in the FNS in an n-pancake graph, (n-2.875)(n-1)!+1.5(n-3)!, and that in an n-burnt pancake graph, 2n-1(n-1)!(n-3.5).

The increasing demand for high-performance computing in recent years has led to active research on massively parallel systems. The interconnection network in a massively parallel system interconnects hundreds of thousands of processing elements so that they can process large tasks while communicating among others. By regarding the processing elements as nodes and the links between processing elements as edges, respectively, we can discuss various problems of interconnection networks in the framework of the graph theory. Many topologies have been proposed for interconnection networks of massively parallel systems. The hypercube is a very popular topology and it has many variants. The cross-cube is such a topology, which can be obtained by adding one extra edge to each node of the hypercube. The cross-cube reduces the diameter of the hypercube, and allows cycles of odd lengths. Therefore, we focus on the cross-cube and propose an algorithm that constructs disjoint paths from a node to a set of nodes. We give a proof of correctness of the algorithm. Also, we show that the time complexity and the maximum path length of the algorithm are O(n3 log n) and 2n - 3, respectively. Moreover, we estimate that the average execution time of the algorithm is O(n2) based on a computer experiment.

This paper proposes an algorithm that solves the node-to-set disjoint paths problem in an n-Möbius cube in polynomial-order time of n. It also gives a proof of correctness of the algorithm as well as estimating the time complexity, O(n4), and the maximum path length, 2n-1. A computer experiment is conducted for n=1,2,...,31 to measure the average performance of the algorithm. The results show that the average time complexity is gradually approaching to O(n3) and that the maximum path lengths cannot be attained easily over the range of n in the experiment.

Conceptual data modeling is an important activity in database design. However, it is difficult for novice learners to master its skills. In the conceptual data modeling, learners are required to detect and correct errors of their artifacts by themselves because modeling tools do not assist these activities. We call such activities self checking, which is also an important process. However, the previous research did not focus on it and/or the data collection of self checks. The data collection of self checks is difficult because self checking is an internal activity and self checks are not usually expressed. Therefore, we developed a method to help learners express their self checks by reflecting on their artifact making processes. In addition, we developed a system, KIfU3, which implements this method. We conducted an evaluation experiment and showed the effectiveness of the method. From the experimental results, we found out that (1) the novice learners conduct self checks during their conceptual data modeling tasks; (2) it is difficult for them to detect errors in their artifacts; (3) they cannot necessarily correct the errors even if they could identify them; and (4) there is no relationship between the numbers of self checks by the learners and the quality of their artifacts.

For any pair of distinct nodes in an n-pancake graph, we give an algorithm for construction of n-1 internally disjoint paths connecting the nodes in the time complexity of polynomial order of n. The length of each path obtained and the time complexity of the algorithm are estimated theoretically and verified by computer simulation.

In this paper, we give an algorithm for the node-to-set disjoint paths problem in rotator graphs with its evaluation results. The algorithm is based on recursion and it is divided into cases according to the distribution of destination nodes in classes into which all the nodes in a rotator graph are categorized. The sum of the length of paths obtained and the time complexity of the algorithm are estimated and verified by computer simulation.

In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-burnt pancake graphs in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n3) and the maximum path length 3n+4. We conducted a computer experiment for n=2 to 100 to measure the average performance of our algorithm. The results show that the average time complexity is O(n3.0) and the maximum path length is 3n+4.

Vocabulary acquisition based on the traditional pen-and-paper approach is outdated, and has been superseded by the multimedia-supported approach. In a multimedia-supported foreign language learning environment, a learning material comprised of a still-image, a text, and the corresponding sound data is considered to be the most effective way to memorize a noun. However, extraction of an appropriate still image for a noun has always been a challenging and time-consuming process for learners. Learners' burden would be reduced if a system could extract an appropriate image for representing a noun. Therefore, the present study purposed to extract an appropriate image for each noun in order to assist foreign language learners in acquisition of foreign vocabulary. This study presumed that, a learning material created with the help of an appropriate image would be more effective in recalling memory compared to the one created with an inappropriate image. As the first step to finding appropriate images for nouns, concrete nouns have been considered as the subject of investigation. Therefore, this study, at first proposed a definition of an appropriate image for a concrete noun. After that, an image re-ranking algorithm has been designed and implemented that is able to extract an appropriate image from a finite set of corresponding images for each concrete noun. Finally, immediate-after, short- and long-term learning effects of those images with regard to learners' memory retention rates have been examined by conducting immediate-after, delayed and extended delayed posttests. The experimental result revealed that participants in the experimental group significantly outperformed the control group in their long-term memory retention, while no significant differences have been observed in immediate-after and in short-term memory retention. This result indicates that our algorithm could extract images that have a higher learning effect. Furthermore, this paper briefly discusses an on-demand learning system that has been developed to assist foreign language learners in creation of vocabulary learning materials.

In this paper, we extend the notion of bijective connection graphs to introduce directed bijective connection graphs. We propose algorithms that solve the node-to-set node-disjoint paths problem and the node-to-node node-disjoint paths problem in a directed bijective connection graph. The time complexities of the algorithms are both O(n4), and the maximum path lengths are both 2n-1.

Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.

In this paper, a dynamic constructive algorithm for fault tolerant feedforward neural network, called DCFTA, is proposed. The algorithm starts with a network with single hidden neuron, and a new hidden unit is added dynamically to the network whenever it fails to converge. Before inserting the new hidden neuron into the network, only the weights connecting the new hidden neuron to the other neurons are trained (i. e. , updated) until there is no significant reduction of the output error. To generate a fault tolerant network, the relevance of each synaptic weight is estimated in each cycle, and only the weights which have their relevance less than a specified threshold are updated in that cycle. The loss of a connections between neurons (which are equivalent to stuck-at-0 faults) are assumed. The simulation results indicate that the network constructed by DCFTA has a significant fault tolerance ability.

A rotator graph was proposed as a topology for interconnection networks of parallel computers, and it is promising because of its small diameter and small degree. However, a rotator graph is a directed graph that sometimes behaves harmfully when it is applied to actual problems. A bi-rotator graph is obtained by making each edge of a rotator graph bi-directional. In a bi-rotator graph, average distance is improved against a rotator graph with the same number of nodes. In this paper, we give an algorithm for the container problem in bi-rotator graphs with its evaluation results. The solution achieves some fault tolerance such as file distribution based information dispersal technique. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into two cases according to the position of the destination node. The time complexity of the algorithm and the maximum length of paths obtained are estimated to be O(n3) and 4n-5, respectively. Average performance of the algorithm is also evaluated by computer experiments.

Recently, research on parallel processing systems is very active, and many complex topologies have been proposed. A burnt pancake graph is one such topology. In this paper, we prove that a faulty burnt pancake graph with degree n has a fault-free Hamiltonian cycle if the number of the faulty elements is n-2 or less, and it has a fault-free Hamiltonian path between any pair of nonfaulty nodes if the number of the faulty elements is n-3 or less.

A minimum feedback node set in a graph is a minimum node subset whose deletion makes the graph acyclic. Its detection in a dependency graph is important to recover from a deadlock configuration. A livelock configuration is also avoidable if a check point is set in each node in the minimum feedback node set. Hence, its detection is very important to establish dependable network systems. In this letter, we give a minimum feedback node set in a trivalent Cayley graph. Assuming that each word has n bits, for any node, we can judge if it is included in the set or not in constant time.