Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 1994 | Published
Journal Article Open

Embedding cube-connected cycles graphs into faulty hypercubes

Abstract

We consider the problem of embedding a cube-connected cycles graph (CCC) into a hypercube with edge faults. Our main result is an algorithm that, given a list of faulty edges, computes an embedding of the CCC that spans all of the nodes and avoids all of the faulty edges. The algorithm has optimal running time and tolerates the maximum number of faults (in a worst-case setting). Because ascend-descend algorithms can be implemented efficiently on a CCC, this embedding enables the implementation of ascend-descend algorithms, such as bitonic sort, on hypercubes with edge faults. We also present a number of related results, including an algorithm for embedding a CCC into a hypercube with edge and node faults and an algorithm for embedding a spanning torus into a hypercube with edge faults.

Additional Information

© Copyright 1994 IEEE. Reprinted with permission. Manuscript received October 5, 1992; revised August 27, 1993. We would like to thank the anonymous referees for their helpful comments and suggestions.

Attached Files

Published - BRUieeetc94.pdf

Files

BRUieeetc94.pdf
Files (1.2 MB)
Name Size Download all
md5:eda2f72d6bfb58d23c5c48cc7d6b9cbe
1.2 MB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 17, 2023