跳到主要內容

臺灣博碩士論文加值系統

(54.225.48.56) 您好!臺灣時間:2022/01/19 21:39
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:黃文增
研究生(外文):Wen-Tzeng Huang
論文名稱:雙扭超方體, 交錯超方體, 和梅式超方體之容錯漢米爾頓性質
論文名稱(外文):Fault-Tolerant Hamiltonicity of Twisted cubes, Crossed cubes, and Möbius Cubes
指導教授:徐力行徐力行引用關係譚建民譚建民引用關係
指導教授(外文):Lih-Hsing HsuJimmy J. M. Tan
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:107
中文關鍵詞:hamiltonianhamiltonian connectedfault-toleranttwisted cubecrossed cubemobius cube
外文關鍵詞:漢米爾頓漢米爾頓連結容錯雙扭超方體交錯超方體梅氏超方體
相關次數:
  • 被引用被引用:0
  • 點閱點閱:232
  • 評分評分:
  • 下載下載:14
  • 收藏至我的研究室書目清單書目收藏:0
一個 n 維雙扭超方體 (twisted cube),TQn,是超方體 (hypercube) 的一種變形。在本論文中,我們首先提出建構偶數維度 (even-dimension-al) 雙扭超方體的建構法則。我們也探討在受傷 (faulty) 雙扭超方體中的漢米爾頓性質 (fault-tolerant amiltonicity)。令受傷集合 F 是 V(TQn) 連集 E(TQn) 的子集合。我們證明 TQn-F 仍然是漢米爾頓圖形(hamiltonian),假如 |F| 大於等於 n-2。更進一步,我們證明在 V(TQn)-F 中給定任意兩節點 u 和 v,存在有一條漢米爾頓路徑(hamiltonian path) 於 XQn-F 中,假如 |F| 大於等於 n-3。TQn 的容錯漢米爾頓性質是 n-2 和容錯漢米爾頓連結性質 (fault-tolerant hamiltonian connectivity) 是 n-3,這兩者的結果都是最佳的。
類似的,一個 n 維交錯超方體 (crossed cube) 與梅氏超方體 (Möbiu cube) 兩者都是超方體的變形。在本論文中,我們證明最長漢米爾頓路徑能被建立在交錯超方體與梅氏超方體中。最特別的,在受傷交錯超方體與梅氏超方體中,我們證明在任意一對節點之間存在有一條漢米爾頓路徑。主要的,我們證明受傷交錯超方體與梅氏超方體包含 n-2 損壞 (faults),仍然是漢米爾頓圖形。換句話說,長度是2n - fv 的環型 (ring) 可以被嵌入到受傷交錯超方體與梅氏超方體包含fv 損壞節點和 fe 損壞邊,此fv + fe 大於等於 n - 2 且 n 大於等於 3。最近的一個結果已經證明長度是 2n-2fv 的環型可以被嵌入到受傷超方體中,假設 fv+fe 大於等於 n-1 且 n 大於等於 4,具有一些限制。我們的結果和超方體中比較,證明較長的環型可以被嵌入到交錯超方體與梅氏超方體中且沒有限制。
環型結構 (cycle structure),舉例號誌環 (token ring),也常使用於地區網路 (local network) 的連接架構。而探討環型結構是否可嵌入某特定之網路拓撲架構,一直都是研究的重點問題。一個具有可嵌入環型結構的網路 (pancyclic network),被定義為在這個網路內包含長度由4開始到節點總數之所有的環型。更進一步,應用這三種變形的容錯漢米爾頓連結度性質,我們證明它們都是環型結構的網路。
An n-dimensional twisted cube, TQ_n, is a variant of the hypercube. In this Dissertation, we first propose a construction
method for even-dimensional twisted cubes. We also discuss the
hamiltonian properties of faulty twisted cubes. Let the faulty set F be a subset of V(TQ_n) union E(TQ_n). We prove that TQ_n -
F remains hamiltonian if |F| less than and equal to n-2. Moreover, we prove that given any two vertices u and v in
V(TQ_n)-F there exists a hamiltonian path in TQ_n-F, if |F| less than and equal to n-3. Both of these two results are optimum in that the fault-tolerant hamiltonicity of TQ_n is at most n-2 and the hamiltonian connectivity of TQ_n is at most n-3.
Similarly, both of an n-dimensional crossed cube, CQ_n, and an
n-dimensional Mobius cube, MQ_n, are also variants of hyper-cubes according to specific rules. In this Dissertation, we showed that the longest fault-tolerant hamiltonian paths can be
established in crossed cubes and Mobius cubes. In particular, we showed that there exists a hamiltonian path between any pair of vertices in a faulty CQ_n and a faulty MQ_n with n-3 faults. In addition, we prove that a faulty CQ_n and a faulty MQ_n remain hamiltonian with n-2 faults. That is, a ring of length 2^n-f_v can be embedded in a faulty CQ_n and a faulty MQ_n with f_v faulty nodes and f_e faulty edges, where f_v + f_e less than or equal to n-2 and n greater than or equal to 3. A recent result has shown that a ring of length 2^n-2f_v can be embedded in a faulty hypercube, if f_v+f_e less than or equal to n-1 and n greater than or equalto 4, with a few additional constraints. Our results, in comparison to hypercubes, show that longer rings can be embedded in CQ_n and MQ_n without additional constraints.
Cycle structure, for example token ring, is often used as a
connection structure for local area network. The problem of
embedding a ring into different topologies of network is always an important topic research. A pancyclic network is defined to be a network that contains cycles from 4 to the total number of nodes in the network. Furthermore, using the hamiltonian connected property of these three variants, we show that they are all pancyclic networks.
According to our thesis.
S. Abraham and K. Padmanabhan, ''The Twisted Cube Topology
for Multiprocessors: A Study in Network Asymmetry,'''' {\it J. of
Parallel Distributed Computing, } Vol. 13, pp. 104--110, 1991.
E. Abuelrub, and S. Bettayeb,
''Embedding of complete binary trees in twisted hypercubes,'''' in
{\it Proceedings of International Conference on Computer
Applications in Design, Simulation, and Analysis, } pp. 1--4,
1993.
S. B. Akers and B. Krishnamurthy, ''A group-therretic model
for symmetry interconnection networks,'''' {\it IEEE Trans.
Computers, } Vol. 38, No. 4, pp. 555--566, April 1989.
R. Aleliunas and A. L. Rosenberg,
''On Embedding Rectangular Grids in Square Grids,'''' {\it IEEE
Trans. Computers, } Vol. c--31, No. 9, pp. 907--913, Sept. 1982.
L. N. Bhuyan and D. P. Agrawal,
''Generalized Hypercube and Hyperbus Structures for a Computer
Network,'''' {\it IEEE Trans. Computers, } Vol. c--33, No. 4, pp.
323--333, April 1984.
J. A. Bondy and U. S. R. Murty,
{\it Graph Theory with Applications, } North Holland, New York,
1980.
C. P. Chang, J. N. Wang, and L. H. Hsu,
''Topological properties of twisted cube,'''' {\it Information
Sciences, } Vol. 113, pp. 147--167, 1999.
C. P. Chang, T. Y. Sung, and L. H. Hsu,
''Edge Congestion and Topological Properties of Crossed Cubes,''''
{\it IEEE Trans. Parallel and Distributed Systems, } Vol. 11, No.
1, pp. 64--80, Jan. 2000.
P. Cull and S. M. Larson,
''On generalized twisted cubes,'''' {\it Information Processing
Letters, } 55, pp. 53--55, 1995.
P. Cull, and S. M. Larson, ''The M$\rm\ddot{o}$bius
Cubes,'''' {\it IEEE Trans. Computers, } Vol. 44, No. 5, pp.
647--659, May 1995.
K. Day and A. E. AI-Ayyoub,
''Fault Diameter of $k$-ary $n$-cube Networks,'''' {\it IEEE Trans.
Parallel and Distributed Systems, } Vol. 8, No. 9, pp. 903--907,
Sept. 1997.
Douglas B. West, {\it Introduction to graph theory, }
Prentice-Hall, 1996.
D. R. Duh and G. H. Chen and D. F. Hsu,
''Combinatorial Properties of Generalized Hypercube Graphs,'''' {\it
Information Processing Letters, } 57, pp. 41--45, 1996.
K. Efe, ''A Variation on the Hypercube with Lower Diameter,'''' {\it IEEE
Trans. Computers, } Vol. 40, No. 11, pp. 1312--1316, Nov. 1991.
K. Efe, ''The Crossed Cube Architecture for Parallel Computation,'''' {\it
IEEE Trans. Parallel and Distributed Systems, } Vol. 3, No. 5, pp.
513--524, Sept. 1992.
J. Fan, ''Diagnosability of the M$\rm\ddot{o}$bius
Cubes,'''' {\it IEEE Trans. Parallel and Distributed Systems, } Vol.
9, No. 9, pp. 923--928, Sept. 1998.
F. Harary,
{\it Graph theory, } Addison-wesley, Massachusetts, 1972.
P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. van de Snepscheut,
''The twisted cube, in Parallel Architectures and Languages
Europe,'''' {\it Lecture Notes in Computer Science, } pp. 152--159,
1987.
S. Y. Hsieh, G. H. Chen, and C. W. Ho,
''Fault-Free Hamiltonian Cycles in Faulty Arrangement Graphs,''''
{\it IEEE Trans. Parallel and Distributed Systems, } Vol. 10, No.
3, pp. 223--237, Mar. 1999.
S. Y. Hsieh, G. H. Chen, and C. W. Ho,
''Longest Fault-Free Paths in Star Graphs with Edge Faults,'''' {\it
IEEE Trans. Computers, } Vol. 50, No. 9, pp. 960--971, Step. 2001.
D. F. Hsu,
''On Container Width and Length in Graphs, Groups, and Networks,''''
{\it IEICE Trans. on Fundamentals, } Vol. E77-A, No. 4, pp.
668--680, 1994.
W. T. Huang, Y. C. Chuang, J. M. Tan, and L. H.
Hsu, ''Fault-Free Hamiltonian Cycle in Faulty M$\rm\ddot{o}$bius
Cubes,'''' {\it J. of Computing and Systems, } Vol. 4, pp. 106--114,
2000.
W. T. Huang, J. M. Tan, C. N. Hung, and L. H. Hsu
''Fault-Tolerant Hamiltonicity of Twisted Cubes,'''' {\it J. of
Parallel and Distributed Computing, } Accepted, 2001.
W. T. Huang, Y. C. Chuang, J. M. Tan, and L. H. Hsu,
''On the Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes,''''
{\it IEICE Trans. on Fundamentals, } Summitted under revision,
2001.
A. Kanevsky and C. Feng,
''On the embedding of cycles in pancake graphs,'''' {\it Parallel
Computing, } Vol. 21, pp. 923--936, 1995.
H. C. Keh and J. C. Lin,
''On fault-tolerant embedding of Hamiltonian cycles, linear arrays
and rings in a Flexible Hypercube,'''' {\it Parallel Computing, }
Vol. 26, pp. 769--781, 2000.
P. Kulasinghe and S. Betayeb,
''Embedding Binary Trees into Crossed Cubes,'''' {\it IEEE Trans.
Computers, } Vol. 44, No. 7, pp. 923--929, July 1995.
S. Latifi, S. Q. Zheng, and N. Bagherzadeh,
''Optimal ring embedding in hypercubes with faulty links,'''' {\it
Proceedings of the IEEE Symposium on Fault-Tolerant Computing, }
Vol. 42, pp. 178--184, 1992.
F. T. Leighton,
{\it Introduction to Parallel Algorithms and Architectures: Array,
Tree, Hypercubes, } San Mateo, Calif.: Morgan Kaufmann, 1992.
Y. R. Leu and S. Y. Kuo,
''Distributed Fault-Tolerant Ring Embedding and Reconfiguration in
Hypercubes,'''' {\it IEEE Trans.\ Computers, } Vol. 48, No. 1, pp.
81--88, Jan. 1999.
R. S. Lo and G. H. Chen,
''Embedding Hamiltonian Paths in Faulty Arrangement Graphs with
the Backtracking Method,'''' { \it IEEE Trans. Parallel and
Distributed Systems,} Vol. 12, No. 2, pp. 209--221, Feb. 2001.
R. S. Lo and G. H. Chen,
''Embedding Longest Fault-Free Paths in Arrangement Graphs with
Faulty Vertices,'''' {\it Networks, } Vol. 37(2), pp. 84--93, 2001.
G. M. Megson, X. Liu, and X. Yang,
''Fault-Tolerant Ring Embedding in a Honeycom Torus with Node
Failures,'''' { \it Parallel Processing Letters, } Vol. 9, No. 4,
pp. 551--561, 1999.
H. Sarbazi-Azad, M. Ould-Khaoua, and L. M. Mackenzie,
''Algorithm construction of Hamiltoniana in pyramids,'''' { \it
Information Processing Letters,} 80, pp. 75--79, 2001.
R. A. Rowley and B. Bose,
''Fault-Tolerant Ring Embedding in de Bruijn Networks,'''' { \it
IEEE Trans. Computers, } Vol. 42, No. 12, pp. 1480--1486, Dec.
1993.
Y. Saad and M. H. Schultz,
''Topological Properties of Hypercubes,'''' {\it IEEE Trans.
Computers, } Vol. 37, No. 7, pp. 867--872, July 1988.
A. Sengupta,
''On ring embedding in hypercubes with faulty nodes and links,''''
{\it Information Processing Letters, } 68, pp. 207--214, 1998.
T. Y. Sung, C. Y. Lin, Y. C. Chuang, and L. H. Hsu,
''Fault tolerant token ring embedding in double loop networks,''''
{\it Information Processing Letters, } 66, pp. 201--207, 1998.
Y. C. Tseng,
''Embedding a ring in a hypercube with both faulty links and
faulty nodes,'''' {\it Information Processing Letters, } 59, pp.
217--222, 1996.
Y. C. Tseng, S. H. Chang, and J. P. Sheu,
''Fault-Tolerant Ring Embedding in a Star Graph with Both Link and
Node Failures,'''' {\it IEEE Trans. Parallel and Distributed
Systems, } Vol. 8, No. 12, pp. 1185--1195, Dec. 1997.
M. D. Wagh and J. Mo
''Hamilton cycles in Trivalent Cayley graphs,'''' {\it Information
Processing Letters, } 60, pp. 177--181, 1996.
A. Y. Wu,
''Embedding of Tree Networks into Hypercubes,'''' {\it J. of
Parallel and Distributed Computing, } Vol. 2, No. 3, pp. 238--249,
Aug. 1985.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文