On the Embedding of Cycles in Pancake Graphs

Document Type

Article

Publication Date

6-1-1995

Department

Computing

School

Computing Sciences and Computer Engineering

Abstract

In recent times the use of star and pancake networks as a viable interconnection scheme for parallel computers has been examined by a number of researchers. An attractive feature of these two classes of graphs is that they have sublogarithmic diameter and have a great deal of symmetry akin to the binary hypercube. In this paper we describe new algorithms for embedding: (a) Hamiltonian cycles along with ranking and unranking algorithms with respect to them, and (b) The set of cycles. The analogous problems for star graphs has been solved recently [5].

Publication Title

Parallel Computing

Volume

21

Issue

6

First Page

923

Last Page

936

Link to Full Text

Find in your library

Share

COinS