二元樹完美嵌入超立方體的上界

Upper Bounds on Perfect Embedding Binary trees to Hypercubes

盧威龍(Wei-Lung Lu)

指導教授 ： 王有禮

國立暨南國際大學/科技學院/資訊工程學系/碩士(2008年)

https://doi.org/10.6837/NCNU.2008.00224

摘要

超立方體與二元樹都是被熱門研究的網路架構，因為它們擁有良好的性質。如超立方體有高連通值(strong connectivity)、低直徑(low diameter)、有規律性(regularity)與對稱性(symmetry) ，可以被許多其它網路架構嵌入。二元樹是一個許多演算法所使用的資料結構，如分而治之(divide and conquer)等。尤其在資料庫上的一些演算法更可以在以樹為主的資料結構上得到相當好的執行效率。在平行計算(parallel computation)理論中，圖形的嵌入是一個相當重要的議題。二元樹可以嵌入至超立方體意指一些專門設計給二元樹的演算法能夠轉移至超立方體網路結構上順利地實行。
如果我們能夠藉由點數就能判斷是否能嵌入，則我們可以省去嘗試將點數過多的情況卻總是無法嵌入的時間。本篇論文主要研究的問題就是判斷特定點數的二元樹是否能嵌入它的最似超立方體，我們的研究證明了在點數小於12的二元樹時，均可以嵌入。某些特定點數的二元樹不能嵌入。並更進一步提出一個推測，我們證明了，若此推測為真，則Bhatt等人的推測也為真。

關鍵字

超立方體 ； 最似超立方體 ； 次似超立方體 ； 二元樹 ； 嵌入 ； 完美嵌入

並列摘要

Both hypercubes and binary trees are well studied interconnection networks, because both of them have good properties. For example, hypercubes have properties of strong connectivity, low diameter, regularity and symmetry and they can also be embedded by many other interconnection networks. Binary trees are used as data structures for many algorithms. Especially, they are used on data base algorithms in order to of data base get efficiency. In parallel computation, it is an important issue to embed binary trees to hypercubes, because the existence of such an embedding demonstrates the ability of a hypercube-formed interconnection network to simulate an algorithm which is designed for a binary tree. If we can determine whether there exists such an embedding though the number of verities of the given binary tree, then we can avoid wasting time on trying to embed the given binary tree. In this paper, we study the problem that whether we can embed a binary tree with a specific order to its optimal hypercubes. We prove that any binary tree with order small than 12 can be embedded to its optimal hypercubes. Furthermore, for the conjecture of Bhatt et al. at 1985, we proposed another conjecture. We also proved that if the conjecture is true, the Bhatt's conjecture is true as well.

並列關鍵字

hypercubes ； optimal hypercube ； next-to-optimal hypercube ； binary trees ； embedding ； perfect embedding

參考文獻

[1] R.Balakrishnan and K. Ranganatha, A Textbook of Graph Theory, Springer , 2000

[2] J. L. Bentley, and H. T. Kung, "A tree machine for searching problems," Proceedings of International Conference on Parallel Processing, pp. 257-266, 1979.

[3] Saïd Bettayeb, Priyalal Kulasinghe, "Embedding Binary Trees into Crossed Cubes," IEEE Transactions on Computers, Volume 44, Issue 7, pp. 923 - 929, 1995

[4] S. Bezrukov, B. Monien,W. Unger, G.Wechsung, "Embedding caterpillars into the hypercube," Technical Report, University of Paderborn, 1995.

[5] S. N. Bhatt, and I. C. F. Ipsen, "How to embed trees in hypercubes," Yale University Res. Rep., RR-443, Dec. 1985.