Embed longest rings onto star graphs with vertex faults
Resource
Parallel Processing, 1998. Proceedings. 1998 International Conference on
Journal
1998 International Conference on Parallel Processing
Pages
-
Date Issued
1998-08
Date
1998-08
Author(s)
DOI
N/A
Abstract
The star graph has been recognized as an attractive alternative to the hypercube. Let Fe and Fν be the sets of vertex faults and edge faults, respectively. Previously, Tseng et al. showed that an n-dimensional star graph can embed a ring of length n! if |Fe|≤n-3 (|Fν|=0), and a ring of length at least n!-4|Fν| if |Fν|≤n-3 (|Fe|=0). Since an n-dimensional star graph is regular of degree n-1 and is bipartite with two partite sets of equal size, our result achieves optimality in the worst case. © 1998 IEEE.
Other Subjects
A-RINGS; Edge faults; Equal sizes; Hypercube; Optimality; Partite sets; Star graphs
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
00708473.pdf
Size
81.39 KB
Format
Adobe PDF
Checksum
(MD5):7f42acbae97d76ab0d12ff2acf65baf7