An O(log(N)) algorithm for the h-extra edge connectivity of bijection connection networks

 报告题目: An O(log(N)) algorithm for the h-extra edge connectivity of bijection connection networks

 报  告  人:张明祖

 报告时间:2017年10月26日(星期四)下午15:10

 报告地点:第三办公区202室


 报告摘要:

In parallel and distributed systems, the methods of massive data storage and massive data processing are highly affected by topological parameters of the underlying interconnection networks of the given systems.

To give a quantitative indicator of fault-tolerant of n-dimensional bijective connection Bn in presence of failing links, the h-extra edge-connectivity of Bn on N=2^n processors, λh(Bn), is investigated for each well-defined h≤N/2 in this paper, which is the minimum number of faulty links whose removal disconnects the networks such that every obtained component has at least h processors. For each h≤N/2, an O(log(N)) algorithm is designed to determine exact values of λh(Bn), which improves several recent results.

Since Bn contains networks like hypercube, twisted cube, crossed cube, Mobius cube and so on, the corresponding problems of the members of this class of networks will be solved as byproducts.


 报告人介绍:

张明祖,厦门大学,西弗吉尼亚大学联合培养博士生。已在Information Science, Theoretical Computer Science等知名期刊发表SCI论文4篇,另有9篇论文已投稿SCI期刊