| Title | Uniform emulations of two different types of shuffle-exchange networks |
|---|---|
| Published in | RUU-CS, Vol. 84-09. |
| Author | Bodlaender, H.L. |
| Date | 2007-07-11 |
| Language | English |
| Type | report |
| Publisher | Utrecht University |
| Abstract | Uniform network emulations are a method t o obtain efficient and structure preserving simulations of large networks on smaller networks. There are two slightly different types of graphs, both realizing Stone's concept of a shuffle-exchange network: the (classical) shuffle exchange graph and the 4-pin shuffle. We analyze the uniform emulations both types of graphs allow, give a complete characterisation of the possible uniform emulations of the (classical) shuffle-exchange graph with 2n nodes on itself and on the 4-pin shuffle with 2n-1 nodes, and show that the 4-pin shuffle allows uniform emulations in instances where the (classical) shuffle-exchange graph does not. |
| Publication | http://igitur-archive.library.uu.nl/math/2007-0711-200445/UU... |
| Persistent Identifier | URN:NBN:NL:UI:10-1874-21988 |
| Metadata | XML |
| Repository | Utrecht University |
Go to page top
Go back to contents
Go back to site navigation