A temporal bipartite graph is a graph model that incorporates time-related information into its edges, making it suitable for modeling real-world phenomena like disease outbreaks. However, this temporal information is often sensitive. To protect the privacy of graph data, researchers have explored various approaches to preserve privacy in graph queries, with reachability queries being popular and fundamental as they determine the possibility of reaching one node from others in a graph. While privacy-preserving reachability queries have been extensively studied, existing efforts often overlook the valuable attribute information present in both edges and nodes of the graphs. Moreover, reachability queries on temporal bipartite graphs have not received sufficient attention in the literature. To bridge this gap, we propose a novel approach to achieve various privatereachabilityqueries onstructured encryptedtemporalbipartitegraphs ($\mathsf{RQ}$-$\mathsf{STBG}$) through a real-world scenario. Specifically, we construct a minimal index using hierarchical 2-hop labels and integrate structured encryption, order-revealing encryption, and garbled Bloom filters to support reachability queries with different label constraints. The proposed scheme is flexible and can cater to the query requirements of diverse users. Security analysis and experimental evaluations demonstrate that the proposed scheme achieves both preferable security and efficiency.

Fault diagnosability can reflect the actual self diagnosing capability of a multiprocessor system better. However, people usually focus on the overall information and neglect the important local information. In order to reflect the locality of a system at a node better, this paper proposes a novel fault diagnosis strategy, called x-block local fault diagnosability (x-BLFD), where the x-block condition requires more than x connected fault-free nodes. Then, we characterize some important properties about the x-BLFD of multiprocessors interconnected networks under the Preparata/Metze/Chien model (P/M/C), and further propose the x-BLFD in an$f(x)$-extended block network with the minimum$(x+1)$-subnetwork degree at some node. We also establish an approximate algorithm to calculate the x-BLFD of a large-scale diagnosable network at some node, and analyze the experimental performance of large-scale networks. Furthermore, we apply our proposed conclusion to obtain the x-BLFD of 16 well-known networks at some node directly under P/M/C, including dual cubes, hierarchical cubic networks, DQcubes, twisted hypercubes, Bicube networks, crossed cubes, folded hypercubes, k-ary n-cubes, balanced hypercubes, BC graphs,$(n,k)$-star graphs, Cayley graphs generated by transposition trees, bubble-sort star graphs, split-star networks, data center networks, and$(n,k)$-arrangement graphs. Finally, we compare the x-BLFD with the diagnosability, conditional diagnosability, pessimistic diagnosability, and$t/k$-diagnosability by a large number of detailed numerical analysis. It can be seen that the x-BLFD is greater than all the other types of fault diagnosabilities.

The shortest distance query is used to determine the shortest distance between two vertices. Various graph encryption schemes have been proposed to achieve accurate, efficient and secure shortest distance queries for encrypted graphs. However, the majority of these schemes are inefficient or lack scalability due to the time-consuming index construction and large index storage. Moreover, none of them consider the trade-off between query efficiency and accuracy. To better trade off the query efficiency and accuracy, we propose a Pruned Pendant Vertex based Index for Shortest Distance Query ($\mathsf { PPVI}$-$\mathsf { SDQ}$) under structured encryption. The proposed scheme utilizes the structured encryption technique to encrypt a graph and build indexes. The main idea is to use the recursive method to repeatedly prune the pendant vertex, and thereby reducing the index size and construction time by minimizing the redundant data storage and graph traversal. The proposed scheme achieves accurate, efficient and secure shortest distance query with privacy-preserving for encrypted graph. The security analysis demonstrates that the proposed scheme satisfies CQA2-security. Experimental results with real datasets show that the scheme achieves the optimal accuracy and efficiency.

Abstract Diagnosability is an important metric to fault tolerance and reliability for multiprocessor systems. However, plenty of research on fault diagnosability focuses on node failure. In practical scenario, not only node failures take place but also link malfunctions may arise. In this work, we investigate the diagnosability of general regular networks with failing nodes as well as missing malfunctional links. Let $S$ be a set of the missing links and broken-down nodes. We first prove that the diagnosability of the survival graph $G\setminus S$ persists $\delta (G\setminus S)$ under the PMC model (Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the connection assignment problem of diagnosable systems. IEEE Trans. Electron. Comput., EC-16, 848–854) for a $t$-regular and $t$-connected triangle-free network $G$ subject to $|S|\leq t-1$ and $|V(G)|\geq 3t-2$ ($t\geq 3$). Furthermore, we determine the diagnosability of $G\setminus S$ for some kinds of extensively explored $t$-regular networks with triangles subject to $|S|\leq t-1$ ($t\geq 3$).

Abstract In this paper, we propose a new digragh model for system level fault diagnosis, which is called the $(f_1,f_{2})$-bounded Preparata–Metze–Chien (PMC) model (shortly, $(f_1,f_{2})$-BPMC). The $(f_1,f_{2})$-BPMC model projects a system such that the number of faulty processors that test faulty processors with the test results $0$ does not exceed $f_{2}$$(f_2\leq f_{1})$ provided that the upper bound on the number of faulty processors is $f_{1}$. This novel testing model compromisingly generalizes PMC model (Preparata, F.P., Metze, G. and Chien R.T. (1967) On the connection assignment problem of diagnosable systems. IEEE Tran. Electron. Comput.,EC-16, 848–854) and Barsi–Grandoni–Maestrini model (Barsi, F., Grandoni, F. and Maestrini, P. (1976) A theory of diagnosability of digital systems. IEEE Trans. Comput.C-25, 585–593). Then we present some characterizations for one-step diagnosibility under the $(f_1,f_{2})$-bounded PMC model, and determine the diagnosabilities of some special regular networks. Meanwhile, we establish the characterizations of $f_1/(n-1)$-diagnosability and three configurations of $f_1/(n-1)$-diagnosable system under the $(f_1,f_{2})$-BPMC model.

As a critical parameter in evaluating the reliability of a multiprocessor system when processors malfunction, the \boldmath h-extra connectivity (h-EC) of a multiprocessor system modeled by a graph G, denoted by κo(h)(G), is an h-extra vertex-cut with minimum cardinality. Both of the h-extra conditional diagnosability (h-ECD) and the t/h-diagnosability of the multiprocessor system are vital to tolerate and diagnose faulty processors. These two parameters rely on the resolving of hEC. For the multiprocessor system based on star graph Sn, we show that the 5-EC κo(5)(Sn) of Sn(n ≥ 5) is 6n - 18. As a by-product, we present a novel proof of κo(2)(Sn) = 3n - 7 (resp., κo(4)(Sn) = 5n - 14) by relaxing the restriction n ≥ 10 (resp., n ≥ 7) to n ≥ 5 (resp., n ≥ 5). Furthermore, we determine that the h-ECD of Sn(n ≥ 5) under the preparata, metze, and chien (PMC) model is (h + 1)n - 2h - 1 for 1 ≤ h ≤ 3 and (h + 1)n - 3h + 2 for 4 ≤ h ≤ 5. In addition, we show that Snis [(h + 1)n - 4h + 2]/h-diagnosable for 4 ≤ h ≤ 5, which extends the result that Snis [(h + 1)n - 3h - 1]/h-diagnosable for 1 ≤ h ≤ 3 by [Zhou et al. “The t/k-diagnosability of star graph networks,” IEEE Trans. Comput., vol. 64, no. 2, pp. 547-555, Feb. 2015].