Spanning subgraphs with applications to communication on a subclass of the Cayley-graph-based networks Original Research Article

In this paper, we develop a special framework on a number of networks that exhibit some specific characteristics and belong to a subclass of the Cayley-graph-based networks. Subsequently, we show how this framework can be used to construct on all the applicable networks a spanning subgraph, denoted by BSG, that possesses several special properties. This spanning subgraph constitutes the basic tool for the development of algorithms for three fundamental communication problems on interconnection networks, namely, the multinode broadcasting, and the single-node and multinode scattering. The algorithms are developed in the store-and-forward, all-port, and bidirectional communication model and are analyzed according to the constant cost model.