WCSE 2016
ISBN: 978-981-11-0008-6 DOI: 10.18178/wcse.2016.06.011

Tolerating One and Two Node Failures in a Bipartite Network K(n,n)

Abdel Aziz (Zizo) Farrag

Abstract— To achieve fault tolerance in a parallel or a distributed network, some spare processors and extra links can be added so that the network can continue to operate even in the presence of some failures. However, due to the limitation on the number of links adjacent to a node in a VLSI design, it is important to minimize the node-degree of the whole network. We use this criteria to develop optimal solutions for tolerating one and two node failures in the bipartite graph K(n,n). This configuration includes, as special cases, some important networks (such as stars and trees), and moreover, it was used in modeling many important applications (e.g., matching, scheduling, coding, etc.).

Index Terms— fault tolerance, network, graph, bipartite network.

Abdel Aziz (Zizo) Farrag
Faculty of Computer Science, Dalhousie University, CANADA


Cite: Abdel Aziz (Zizo) Farrag, "Tolerating One and Two Node Failures in a Bipartite Network K(n,n)," Proceedings of 2016 6th International Workshop on Computer Science and Engineering, pp. 54-59, Tokyo, 17-19 June, 2016.