Name
Abstract | ||
|---|---|---|
Star, bubble-sort, pancake, and Rotator-Faber-Moore (RFM) graphs are well-known interconnection networks that have node symmetric, maximum fault tolerance and hierarchical partition properties. These graphs are widely assumed to improve the network cost of a hypercube. This study proposes embedding methods for a star graph and its variations, and provides an analysis of the relevant costs. Results show that a bubble-sort graph can be embedded in a star graph with dilation 3, and in a RFM graph with dilation 2, while a star graph can be embedded in a pancake graph with dilation 4. The results suggest that the embedding method developed for the bubble-sort graph can be simulated in star graphs and RFM graphs in constant time O(1). |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13136-3_36 | ICA3PP (2) |
Keywords | Field | DocType |
rfm graph,embedding method,star graph,hierarchical partition property,bubble-sort graph,maximum fault tolerance,pancake graph,embedding algorithm,node symmetric,network cost,constant time,fault tolerant,embedding | Block graph,Line graph,Computer science,Star (graph theory),Book embedding,Symmetric graph,Lattice graph,Topological graph theory,Planar graph,Distributed computing | Conference |
Volume | ISSN | ISBN |
6082 | 0302-9743 | 3-642-13135-2 |
Citations | PageRank | References |
2 | 0.39 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mihye Kim | 1 | 74 | 14.31 |
| W. Kim | 2 | 23 | 3.17 |
| Hyeong-Ok Lee | 3 | 86 | 14.71 |