嵌置樹狀結構到超立方體

Abstract

最近幾年來，嵌置問題已受到廣泛地討論。在此篇論文中，我們研究嵌置 各種不同的客人圖形到主人圖形，例如把完全二元樹、不完全二元樹、樹 形機器和四元樹嵌置到超立方體與不完全超立方體中。此外，我們也研究 在一個有缺失的超立方體中，動態地重建完全二元樹。首先，我們使用最 小的不完全超立方體來嵌置完全二元樹，並且保持完全二元樹的相鄰性， 然後在超立方體中嵌置不完全二元樹。第二，我們在有限大小的超立方體 中，最佳地嵌置大型完全二元樹。第三，我們在膨脹值 =1 的條件下，嵌 置樹形機器到不完全超立方體中，然後在負載平衡的條件下，嵌置大型樹 形機器到有限大小的超立方體中。第四，我們嵌置完全四元樹到超立方體 中，並且保持完全四元樹的相鄰性，然後在膨脹值 =1 的條件下，嵌置完 全四元樹到不完全超立方體中。最後，我們在有缺失的超立方體中，使用 動態的重建方法來嵌置完全二元樹，並且重建之後會被影響到的結點數目 ，要儘可能的少。 The embedding problem has been widely discussed in recent years. In this dissertation, we study embedding of various guest graphs such as complete binary trees, incomplete binary trees, tree machines and quadtrees into host graphs such as hypercubes and incomplete hypercubes. We also study dynamic reconfiguration of complete binary trees in faulty hypercubes. First, we embed a complete binary tree into an incomplete hypercube of the smallest size so that the adjacency of the complete binary tree is preserved, and look for an incomplete binary tree in a hypercube. Second, we optimally embed a large complete binary tree into a hypercube of limited size. Third, we embed a tree machine into an incomplete hypercube with expansion 1, and embed a large tree machine into a hypercube of limited size with load-balance. Fourth, we embed a quadtree into a hypercube so that the adjacency of the quadtree is preserved, and embed a quadtree into an incomplete hypercube with expansion 1. Fifth, we dynamically reconfigure to embed a complete binary tree into a faulty hypercube, and the number of the affected nodes of the complete binary tree are as few as possible after reconfiguring.