Embedding of cycles and grids in star graphs
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 540-547
- https://doi.org/10.1109/spdp.1990.143600
Abstract
The use of star graphs as a viable interconnection scheme for parallel computers has been examined by a number of authors. 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. The authors describe a new class of algorithms for embedding Hamiltonian cycle, the set of all even cycles and a variety of two and multi-dimensional grids in a star graph. They derive an algorithm for the ranking and the unranking problem with respect to the Hamiltonian cycle.Keywords
This publication has 3 references indexed in Scilit:
- A group-theoretic model for symmetric interconnection networksIEEE Transactions on Computers, 1989
- Combinatorial AlgorithmsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1989
- Some Topics in Graph TheoryPublished by Cambridge University Press (CUP) ,1986