Conditional Connectivity And Conditional Diagnosability On Some Classes Of Interconnection Networks

With the rapid development of the interconnection network,the reliability of the interconnection network has been widely concerned.The topological structure of the interconnection network can be represented by a connected graph where the vertices correspond to processors and the connection between the two processors is regarded as an edge.The connectivity of a graph is an important metric to measure the reliability of the interconnection network.Traditional connectivity can not accurately evaluate the reliability of the interconnection network.Therefore,a variety of concepts of the conditional(edge-)connectivity have been proposed,such as the maximally local(edge-)connectivity,the extra(edge-)connectivity,the component(edge-)connectivity and so on.In the second chapter,we give the edge-fault-tolerant maximally local edge-connectivity,the fault-tolerant one-to-many maximally local connectivity of the augmented cube AQ_n,and the 3-extra connectivity of the enhanced hypercube Q_n,k.The interconnection network which are composed of large-scale processors,it is diffi-cult to ensure that all processors and links are running without fault.In order to ensure the reliability of the interconnection network,it is very important and necessary to find and repair or replace the faulty processors in the network quickly and accurately.In the third chapter,we give the h-edge tolerable diagnosability of the k-regular network under the PMC model,the MM^*model and the(f₁,f₂)-BPMC model,and the f₁-diagnosability under the(f₁,f₂)-BPMC model.In addition,we calculate the probabilistic diagnosabil-ity of clustered of faults for enhanced hypercube-based multiprocessor system by using probability diagnosis algorithm.