EMBEDDING OF CYCLES AND GRIDS IN STAR GRAPHS

Publisher Website
Google Scholar
Abstract
The use of the star graph as a viable interconnection scheme for parallel computers has been examined by a number of authors in recent times. An attractive feature of this class of graphs is that it has sublogarithmic diameter and has a great deal of symmetry akin to the binary hypercube. In this paper we describe a new class of algorithms for embedding (a) Hamiltonian cycle (b) the set of all even cycles and (c) a variety of two- and multi-dimensional grids in a star graph. In addition, we also derive an algorithm for the ranking and the unranking problem with respect to the Hamiltonian cycle.

This publication has 0 references indexed in Scilit: