(3.230.76.48) 您好!臺灣時間:2021/04/15 01:12
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳垂呈
研究生(外文):Chen, Chui-Cheng
論文名稱:嵌置樹狀結構到超立方體
論文名稱(外文):Embedding Trees into Hypercubes
指導教授:陳榮傑陳榮傑引用關係
指導教授(外文):Rong-Jaye Chen
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1996
畢業學年度:84
語文別:英文
論文頁數:88
中文關鍵詞:嵌置二元樹樹形機器四元樹超立方體
外文關鍵詞:EmbeddingBinary treeTree machineQuadtreeHypercube
相關次數:
  • 被引用被引用:0
  • 點閱點閱:90
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
最近幾年來,嵌置問題已受到廣泛地討論。在此篇論文中,我們研究嵌置
各種不同的客人圖形到主人圖形,例如把完全二元樹、不完全二元樹、樹
形機器和四元樹嵌置到超立方體與不完全超立方體中。此外,我們也研究
在一個有缺失的超立方體中,動態地重建完全二元樹。首先,我們使用最
小的不完全超立方體來嵌置完全二元樹,並且保持完全二元樹的相鄰性,
然後在超立方體中嵌置不完全二元樹。第二,我們在有限大小的超立方體
中,最佳地嵌置大型完全二元樹。第三,我們在膨脹值 =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.
Cover
Chinese Abstract
English Abstract
Acknowledgement
Contents
List of Figures
1 Introduction
1.1 Overview of Embedding graphs into Hypercubes
1.2 Outline of the Dissertation
2 Preliminaries
3 Embedding of Binary Trees into Hypercubes
3.1 Embedding of Complete Binary Trees into Smallest Incomplete Hypercubes
3.2 Embedding of Largest Incomplete Binary Trees into Hypercubes
4 Embedding of Large Complete Binary Trees into Hypercubes
4.1 Optimal Embedding of Th into Hh
4.2 Optimal Embedding of Large Complete Binary Trees into Hypercubes
5 Embedding of Trees Machines into Hypercubes
5.1 Embedding of Tree Machine into Inconplete Hypercubes with Expansion
5.2 Embedding of Large Trees Machines into Hypercubes
6 Embedding of Quadtrees into Hypercubes
6.1 Embedding of Quadtrees into Hypercubes with Dilation 1
6.2 Embedding of Quadtrees into Incomplete Hypercubes with Expansion 1
7 Dynamic Reconfiguration of Complete Binary Trees in Faulty Hypercubes
7.1 Reconfiguring of Th in a Faulty Hh+1
7.2 Reconfiguring of Th in Hh+2 with Faults
8 Conclusions
Bibliography
Vita
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔