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.

Hypercubes are a simple topology frequently used as interconnection network of parallel systems. However, hypercubes connecting a significant number of nodes also have an impractically high number of edges. To address this issue, Ghose and Desai introduced a new topology, hierarchical cubic networks, containing almost half many edges than a hypercube of the same size. In this paper, we describe a node-to-set disjoint-path routing algorithm in a hierarchical cubic network HCN(n) finding node-disjoint paths between one source node and k (k≤n+1) destination nodes in O(knlog k) time complexity. Generated paths have lengths of at most 3n+k+3.

The number of Internet-connected devices grows very rapidly, with even fears of running out of available IP addresses. It is clear that the number of sensors follows this trend, thus inducing large sensor networks. It is insightful to make the comparison with the huge number of processors of modern supercomputers. In such large networks, the problem of node faults necessarily arises, with faults often happening in clusters. The tolerance to faults, and especially cluster faults, is thus critical. Furthermore, thanks to its advantageous topological properties, the torus interconnection network has been adopted by the major supercomputer manufacturers of the recent years, thus proving its applicability. Acknowledging and embracing these two technological and industrial aspects, we propose in this paper a node-to-node routing algorithm in an $n$ -dimensional $k$ -ary torus that is tolerant to faults. Not only is this algorithm tolerant to faulty nodes, it also tolerates faulty node clusters. The described algorithm selects a fault-free path of length at most $n(2k+\lfloor k/2\rfloor -2)$ with an $O\left(n^2{k}^2\right|F\left|\right)$ worst-case time complexity with $F$ the set of faulty nodes induced by the faulty clusters.

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.

Japan's largest platform for academic e-journals: J-STAGE is a full text database for reviewed academic papers published by Japanese societies