Characterizations of Minimum Structure- and Substructure-Cuts of Hypercubes. (3rd November 2018)

• Record Type: Journal Article
• Authors: Yang, Yuxing
• Is Part Of: Computer journal. Volume 62:Number 9(2019)
• Page Start: 1313
• Page End: 1321
• Publication Date: 2018-11-03
• Subjects: multiprocessor system -- interconnection network -- hypercube -- structure connectivity -- substructure connectivity; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy115
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: For a graph G and a connected subgraph H of G, denote by ℋ ( G ; H ) the set of subgraphs of G which are isomorphic to H and denote by ℋ S ( G ; H ) the union of sets of subgraphs of T, where T ranges over all the elements in ℋ ( G ; H ) . An H -structure-cut (respectively, H -substructure-cut) of G is a subset of ℋ ( G ; H ) (respectively, ℋ S ( G ; H ) ), if any, whose removal disconnects G . The H -structure connectivity (respectively, H -substructure connectivity) is the cardinality of a minimum H -structure-cut (respectively, H -substructure-cut) of G . The hypercube is one of the most attractive interconnection networks for large-scale multiprocessor computer systems. In this paper, we will characterize the minimum H -structure-cuts and the minimum H -substructure-cuts of hypercubes for H ∈ { K 1, 1, K 1, 2, K 1, 3, C 4 } .