6 June 2018 in IEEE Access
Conditional diagnosability is widely accepted as an important measure in determining the reliability of an interconnection network. The conditional diagnosability of many well-known interconnection networks has been investigated. Exchanged crossed cube(ECQ(s,t)) is a novel variant of hypercube, which retains the advantages of exchanged hypercube and crossed cube in terms of the smaller diameter, fewer links, and lower cost factor, and indicates more balanced consideration among performance and cost. In this paper, several topological properties of ECQ(s,t) are derived. On this basis, the conditional diagnosability of ECQ(s,t) under the PMC model is shown to be 4(s - 1) + 1 for t ≥ s > 2, which is almost two times larger than its classical diagnosability and also is larger than its conditional diagnosability under the MM model.
4 February 2026 in IEEE Transactions on Computers
The traditional, well-known system-level fault diagnosis is to precisely identify faulty nodes in a network via mutual testing between the nodes, and the diagnosability is the maximum allowed number of faulty nodes for correct diagnosis. This paper proposes a new scheme that focuses on detecting whether a given critical substructure (e.g., a specific cycle or path) contains any faulty node. If the detecting outcome is “Yes”, the entire substructure is deemed as faulty, regardless of how many faulty nodes, and where they are in the substructure. This approach is often more cost-effective and technically feasible than pinpointing every faulty node. We name the maximum allowed number of faulty nodes for this strategy to work as the Detectability of the network, as opposed to the diagnosability. We study the detectability for the hypercube $Q_{n}$, under the PMC model. We will show that in $Q_{n}$ ($n\geq 7$), the detectability is $2n-1$ for the minimal bipartite subgraph $K_{1,1}$, and $4n-5$ for the 4-node cycle $C_{4}$. Notably, detectability consistently exceeds traditional diagnosability, tolerating more faulty nodes. We have also designed, validated, and implemented detection algorithms of $O(n\cdot 2^{n-1})$ complexity to detect faulty $K_{1,1}$ and $C_{4}$ in $Q_{n}$. Simulations show a 100% detection rate, with effectiveness maintained even in lower-dimensional $Q_{n}$ where theoretical assumptions do not fully hold.
25 June 2023 in Discrete Applied Mathematics
12 October 2018 in IEEE Access
Exchanged hypercube EH(s,t) is a typical hypercube variant, which is built up by systematically removing a range of edges from hypercube Qs+t+1. EH(s,t) preserves several advantages of hypercube and has better properties in terms of diameter and cost. Diagnosability and conditional diagnosability have been two important measures of selfdiagnostic capability. Normally, conditional diagnosability is several times higher than its diagnosability because conditional diagnosability neglectes the occurrence of low probability. In this paper, we study the properties of EH(s,t) and present some elementary topological and connectivity theorems. Then, Based on the above results, we determine its conditional diagnosability under the MM* model.