A new shortest path routing algorithm and embedding cycles of crossed cube

Abstract

An n-dimensional crossed cube, CQ(n), is a variation of hypercubes. In this paper, we give a new shortest path routing algorithm based on a new distance measure defined herein. In comparison with EFe's algorithm which generates one shortest path in O(n(2)) time, our algorithm can generate more shortest paths in O(n) time. Furthermore, we show that CQ(n) is a pancyclic network and we construct various types of cycles of an arbitrary length at least four.