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 |
Year | DOI | Venue |
---|---|---|
1998 | 10.1109/ICPP.1998.708473 | ICPP |
Keywords | Field | DocType |
embed longest rings,bipartite graph,multiprocessor interconnection networks,edge faults,parallel architectures,fault tolerant computing,optimality,vertex faults,star graphs,graph theory,hypercube,hypercube networks,tree graphs,network topology,computer science,hypercubes,resilience,scattering,star graph | Graph theory,Vertex (geometry),Hypercube graph,Computer science,Folded cube graph,Parallel computing,Bipartite graph,Star (graph theory),Symmetric graph,Hypercube,Distributed computing | Conference |
ISSN | ISBN | Citations |
0190-3918 | 0-8186-8650-2 | 16 |
PageRank | References | Authors |
1.18 | 25 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sun-Yuan Hsieh | 1 | 1715 | 112.85 |
Gen-Huey Chen | 2 | 979 | 89.32 |
Chin-Wen Ho | 3 | 573 | 39.27 |