System diagnosis is process of identifying faulty nodes in a system. An efficient diagnosis is crucial for a multiprocessor system. The BGM diagnosis model is a modification of the PMC diagnosis model, which is a test-based diagnosis. In this paper, we present a specific structure and propose an algorithm for diagnosing a node in a system under the BGM model. We also give a polynomial-time algorithm that a node in a hypercube-like network can be diagnosed correctly in three test rounds under the BGM diagnosis model.

Abstract A graph $G=(V,E)$ is two-disjoint-cycle-cover $[r_1,r_2]$-pancyclic if for any integer $l$ satisfying $r_1 \leq l \leq r_2$, there exist two vertex-disjoint cycles $C_1$ and $C_2$ in $G$ such that the lengths of $C_1$ and $C_2$ are $l$ and $|V(G)| - l$, respectively, where $|V(G)|$ denotes the total number of vertices in $G$. On the basis of this definition, we further propose Ore-type conditions for graphs to be two-disjoint-cycle-cover vertex/edge $[r_1,r_2]$-pancyclic. In addition, we study cycle embedding in the $n$-dimensional locally twisted cube $LTQ_n$ under the consideration of two-disjoint-cycle-cover vertex/edge pancyclicity.

The ability of identifying all the faulty devices in a multiprocessor system is known as diagnosability. The PMC model is the test-based diagnosis with a processor performing the diagnosis by testing the neighboring processors via the links between them. In this paper, we discuss the diagnosability of a ( K 4 – { e})-free graph under the PMC model.

The study of cycle embedding is an important topic in studying the structures of interconnection networks. In this paper, we study the cycles embedding in pancake graphs. We show that every edge in the n-dimensional pancake graph lies on the cycle with every length between 7 to n!.

It is usually difficult to determine the exact reliability of a complicated network system, and numerical estimation may play a critical role in indicating the likelihood that a systemcan be operational in a specified period of time. In this paper, we propose the definition of localized subcube reliability for hypercube-based networks. Using the random fault model and the probability fault model, we derive exact formulations for the localized first-order subcube reliability in an n-dimensional hypercube, respectively. Numerical results are also presented tovalidate the proposed formulations.

Interconnection networks are evolving as a universal approach to solving system-level communication problems in real-world applications. An interconnection network is a programmable system that serves to transport data or messages between components/terminals in a network system. Hypercube is one of the most widely studied network structures for inter-connecting a huge number of network components so that it has long been considered as a good candidate for network architectures. Unidirectional hypercube are obtained from hypercubes by orienting the direction of each edge in a well-defined manner. As routing plays an important role in achieving almost all aspects of network functionalities, this paper makes a theoretical analysis on the channel congestion of the dimension-ordered shortest-path-algorithm with respect to unidirectional hypercubes.

A graph G is pancyclic if it contains a cycle C of every length with 3≤l(C)≤∣V(G)∣⁠, where l(C) denotes the length of C and ∣V(G)∣ denotes the number of vertices in G. In this paper, we propose an augmented pancyclicity problem for the n-dimensional crossed cube CQn, which is a popular variant of the hypercube network. Let dC(u,v) denote the distance between any two distinct vertices u and v traversed by a cycle C in CQn, n≥4⁠. Then, for any integer m with ⌈n+12⌉+1≤m≤2n−1⁠, there exist cycles C of various lengths in CQn such that dC(u,v)=m⁠, where (i) 2m+1≤l(C)≤2n if n is odd and m=⌈n+12⌉+1 and (ii) 2m≤l(C)≤2n otherwise. This result indicates that any two distinct vertices of crossed cubes can be embedded on cycles of various feasible lengths with keeping any feasible distance from each other.

System-level diagnosis is a crucial subject for maintaining the reliability of multiprocessor interconnected systems. Consider a system composed of N independent processors, each of which tests a subset of the others. Under the PMC diagnosis model, Dahbura and Masson proposed an O(N2.5) algorithm to identify the set of faulty processors in a t-diagnosable system, in which at most t processors are permanently faulty. In this paper, we establish some sufficient conditions so that a t-regular system can be conditionally (2t-1)-diagnosable, provided every fault-free processor has at least one fault-free neighbor. Because any t-regular system is no more than t-diagnosable, the approached diagnostic capability is nearly double the classical one-step diagnosability. Furthermore, a correct and complete method is given which exploits these conditions and the presented branch-of-tree architecture to determine the fault status of any single processor. The proposed method has time complexity O(t2), and thus can diagnose the whole system in time O(t2N). In short, not only could the diagnostic capability be proved theoretically, but also it is feasible from an algorithmic perspective.

Diagnosis is an essential subject for the reliability of multiprocessor systems. Under the PMC diagnosis model, Dahbura and Masson [12] proposed a polynomial-time algorithm with time complexity O(N^{2.5}) to identify all the faulty processors in a system with N processors. In this paper, we present a novel method to diagnose a conditionally faulty system by applying the concept behind the local diagnosis, introduced by Somani and Agarwal [30], and formalized by Hsu and Tan [18]. The goal of local diagnosis is to identify the fault status of any single processor correctly. Under the PMC diagnosis model, we give a sufficient condition to estimate the local diagnosability of a given processor. Furthermore, we propose a helpful structure, called the augmenting star, to efficiently determine the fault status of each processor. For an N-processor system in which every processor has an O(\log N) degree, the time complexity of our algorithm to diagnose any given processor is O((\log N)^2), provided that each processor can construct an augmenting star structure of full order in time O((\log N)^2) and the time for a processor to test another one is constant. Therefore, the time totals to O(N(\log N)^2) for diagnosing the whole system.