Wyniki wyszukiwania - BazTech

1

A Local Diagnosis Algorithm for Hypercube-like Networks under the BGM Diagnosis Model

Lin Cheng-Kuan, Kung Tzu-Liang, Chun-Nan Hung, Yuan-Hsiang Teng

Fundamenta Informaticae

|

2022

|

Vol. 185, nr 4

357--373

EN

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.

2

The Diagnosability of(K4 - {e})-free Graphs under the PMC Diagnosis Model

Lin Cheng-Kuan, Kung Tzu-Liang, Wang Dajin, Teng Yuan-Hsiang

Fundamenta Informaticae

|

2020

|

Vol. 177, nr 2

181--188

EN

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 (K4–{e })-free graph under the PMC model.

3

The Conditional-(g, d, k)-Connectivity and Conditional-(g, d, k)-edge-Connectivity on the Hypercubes

Lin Cheng-Kuan, Ma Liang, Fan Jianxi, Hsu Lih-Hsing, Teng Yuan-Hsiang

Fundamenta Informaticae

|

2020

|

Vol. 173, nr 1

33--45

EN

We propose two new measures of conditional connectivity to be the extension of Rg-connectivity and Rg-edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional (g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) degG–F(p) + degG–F(q) ≥ 2g + k for every two distinct vertices p and q in G – F with d(p, q) ≤ d. The (g, d, k)-conditional(-edge)-connectivity, denoted by κg,d,k(λg,d,k), is the minimum cardinality of a conditional (g, d, k)(-edge)-cut. Based on these requirements, we obtain κ1,1,k, κ1,d,2, λ1,1,1 and λ1,d,2 for the hypercubes.

4

Constructing Node-Independent Spanning Trees in Augmented Cubes

Cheng Baolei, Fan Jianxi, Lyu Qiang, Lin Cheng-Kuan, Li Xiaoyan, Chen Guo

Fundamenta Informaticae

|

2020

|

Vol. 176, nr 2

103--128

EN

For a network, edge/node-independent spanning trees (ISTs) can not only tolerate faulty edges/nodes, but also be used to distribute secure messages. As important node-symmetric variants of the hypercubes, the augmented cubes have received much attention from researchers. The n-dimensional augmented cube AQn is both (2n ‒ 1)-edge-connected and (2n ‒ 1)-nodeconnected (n≠3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQn. So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQn is still open. In this paper, we further study the construction principle of the node-ISTs by using the double neighbors of every node in the higher dimension. We prove the existence of 2k − 1 node-ISTs rooted at node 0 in AQn ( 00...0 n – k ) ( n ≥ k ≥ 4 ) by proposing an ingenious way of construction and propose a corresponding O (N logN ) time algorithm, where N = 2k is the number of nodes in AQn ( 00...0 n – k ) .