Anzeige
Erschienen in:
07.01.2019
Paired many-to-many two-disjoint path cover of balanced hypercubes with faulty edges
Erschienen in: The Journal of Supercomputing | Ausgabe 1/2019
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
As a variant of the well-known hypercube, the balanced hypercube \(BH_n\) was proposed as a desired interconnection network topology for parallel computing. It is known that \(BH_n\) is bipartite. Assume that \(S=\{s_1,s_2\}\) and \(T=\{t_1,t_2\}\) are any two sets of vertices in different partite sets of \(BH_n\) (\(n\ge 1\)). It has been proved that there exist two vertex-disjoint \(s_1,t_1\)-path and \(s_2,t_2\)-path of \(BH_n\) covering all vertices of \(BH_n\). In this paper, we prove that there always exist two vertex-disjoint \(s_1,t_1\)-path and \(s_2,t_2\)-path covering all vertices of \(BH_n\) (\(n\ge 2\)) with at most \(2n-3\) faulty edges. The upper bound \(2n-3\) of edge faults can be tolerated is optimal.