局部扭轉超立方體中嵌入兩個互斥多維度網格

Embedding a family of two disjoint multi-dimensional meshes into locally twisted cubes

林政逸(Cheng-Yi Lin)

指導教授 ： 張肇明

國立臺北商業大學/管理學群/商學研究所/碩士(2013年)

https://doi.org/10.6818/NTUB.2013.00010

摘要

LTQn n維度局部扭轉超立方體的簡寫，本篇論文探討如何在局部扭轉超立方體中嵌入兩個互斥多維度網格，本篇論文發展出的方法為：當n>=3以及2<=k<=n時，可以在LTQn中嵌入兩個互斥網格的大小為
2*2*...*2*2^n-k，並且擴張、邊膨脹和邊壅塞都等於1。
{ k-1 }

關鍵字

圖形嵌入 ； 局部扭轉超立方體 ； 多維度網格 ； 連結網路

並列摘要

Let LTQn denote the n-dimensional locally twisted cubes. This thesis deals with the problem of how to embed a family of two disjoint multi-dimensional meshes into locally twisted cubes. We develop the following embeddings: for n >= 3 and 2=k<=n, we show that two disjoint meshes each of size
2*2*...*2*2^n-k
{ k-1 }
can be embedded into LTQn with unit dilation, unit expansion,
and congestion-free. The results obtained are optimal in the sense that the dilations, expansions and congestions of all the embeddings are equal to 1.

並列關鍵字

Graph embedding ； Locally twisted cube ； Multi-dimensional mesh ； Interconnection network

參考文獻

[1] F. Berman and L. Snyder. On mapping parallel algorithms into parallel architectures. Journal of Parallel and Distributed Computing, 4:439–458, 1987.

[2] S. Bokhari. On the mapping problem. IEEE Transactions on Computers, 30:207–2141, 1981.

[3] J.-M. Chang and J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs. Applied Mathematics and Computation, 197:760–767, 2008.

[4] J.-M. Chang, J.-S. Yang, Y.-L. Wang, and Y. Cheng. Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs. Networks, 44:302–310, 2004.

[6] V. Chaudhary and J.K. Aggarwal. Generalized mapping of parallel algorithms onto parallel architectures. Proceedings of the International Conference on Parallel Processing, pages 137–141, 1990.