Optimal Edge Congestion of Exchanged Hypercubes
| Autor: | Y-Chuang Chen, Jimmy J. M. Tan, Tsung-Han Tsai |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Vertex (graph theory)
020203 distributed computing Computer science Distributed computing 0102 computer and information sciences 02 engineering and technology 01 natural sciences Vertex (geometry) Combinatorics Network planning and design Computational Theory and Mathematics 010201 computation theory & mathematics Hardware and Architecture Signal Processing Shortest path problem 0202 electrical engineering electronic engineering information engineering Bipartite graph Algorithm design Hypercube Routing (electronic design automation) Time complexity MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | IEEE Transactions on Parallel and Distributed Systems. 27:250-262 |
| ISSN: | 1045-9219 |
| DOI: | 10.1109/tpds.2014.2387284 |
| Popis: | Topological properties have become a popular and important area of focus for studies that analyze interconnections between networks. The hypercube is one of the most widely discussed topological structures for interconnections between networks and is usually covered in introductions to the basic principles and methods for network design. The exchanged hypercube $\textrm {EH}(s,t)$ is a new variant of the hypercube that has slightly more than half as many edges and retains several valuable and desirable properties of the hypercube. In this paper, we propose an approach for shortest path routing algorithms from the source vertex to the destination vertex in $\textrm {EH}(s,t)$ with time complexity $O(n)$ , where $n=s+t+1$ and $1\le s\le t$ . We focus on edge congestion, which is an important indicator for cost analyses and performance measurements in interconnection networks. Based on our shortest path routing algorithm, we show that the edge congestion of $\textrm {EH}(s,t)$ is $3\cdot 2^{s+t+1}-2^{s+1}-2^{t+1}$ . In addition, we prove that our shortest path routing algorithm is an optimal routing strategy with respect to the edge congestion of $\textrm {EH}(s,t)$ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|