CaltechAUTHORS
  A Caltech Library Service

Embedding cube-connected cycles graphs into faulty hypercubes

Bruck, Jehoshua and Cypher, Robert and Soroker, Danny (1994) Embedding cube-connected cycles graphs into faulty hypercubes. IEEE Transactions on Computers, 43 (10). pp. 1210-1220. ISSN 0018-9340. http://resolver.caltech.edu/CaltechAUTHORS:BRUieeeetc94

[img]
Preview
PDF - Published Version
See Usage Policy.

1151Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BRUieeeetc94

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/12.324546DOIUNSPECIFIED
http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=324546PublisherUNSPECIFIED
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.
Subject Keywords:Cube-connected cycles; fault tolerance; graph embedding; gray code; mesh; parallel computing; fault tolerant computing; hypercube networks; reliability; ascend-descend algorithms; bitonic sort; cube-connected cycle graphs; faulty hypercubes; spanning torus
Record Number:CaltechAUTHORS:BRUieeeetc94
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:BRUieeeetc94
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:12168
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:28 Oct 2008 16:33
Last Modified:26 Dec 2012 10:27

Repository Staff Only: item control page