簡易檢索 / 詳目顯示
| 研究生： |
王俊奕 Wang, Jun-Yi |
|---|---|
| 論文名稱： |
排列圖上漢彌爾頓路徑容錯嵌入之研究 Fault-tolerant Hamiltonian Path embedding on Arrangement Graphs |
| 指導教授： |
謝孫源
Hsieh, Sun-Yuan |
| 學位類別： |
碩士 Master |
| 系所名稱： |
電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering |
| 論文出版年： | 2005 |
| 畢業學年度： | 93 |
| 語文別： | 英文 |
| 論文頁數： | 40 |
| 中文關鍵詞： | 互聯網路 、排列圖 、漢彌爾噸路徑 、容錯嵌入 |
| 外文關鍵詞： | Graph-theoretic interconnection networks, Hamiltonian path, the arrangement graph, fault-tolerant embedding |
| 相關次數： | 點閱：137 下載：1 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
排列圖An,k是可歸納於星狀圖中的一種圖形集合。我們令F包含V(An,k)為錯點的集合。在這一篇論文中，我捫將證明在n-k大於等於2且所以錯點總和小於等於2k(n-k)-5的情況下，且每個點至少有兩個好邊的情況下，An,k具有漢彌爾噸路徑。我們的結果在最差狀況下為最理想結果。
The arrangement graph An,k is a generalization of the star graph. Let FV(An,k) be the set of vertex faults. In this paper, we show that An,k for n-k more then 2, contains a fault-free Hamiltonian path when |F| loss than 2k(n-k)-5 and each vertex is incident to at least two fault-free edges. Our result is optimal in the worst case.
S.B. Akers, D. Harel, and B. Krishnamurthy, "The Star Graph: An Attractive Alternative to the n-Cube," Proc. Int'l Conf. Parallel Processing, pp. 216--223, 1986.
S.B. Akers and B. Krishnamurthy, "A Group-Theoretic Model for Symmetric Interconnection Netwoeks, "IEEE Trans. Computers, vol. 38,no. 4, pp.555--566, Apr. 1989.
J.A. Bondy and U.S.R. Murty, Graph Theory with Applications. New York: North Holland, 1980.
M.Y. Chan and S.J. Lee, "On the Existence of Hamiltonian Circuits in Fauly Hypercubes, "SIAM J.Discrete Math., vol.4, no.4, pp. 511--527, Nov. 1991.
W.K. Chiang and R.J. Chen, "On the Arrangement Graph, "Information Processing Letters, vol. 66, pp. 215--219, 1998.
K. Day and A. Tripathi, "Arrangement Graphs: A class of Generalized Star Graphs, "Information Processing Letters, vol. 42, no. 5, pp. 235--241, 1992.
K. Day and A. Tripathi, "Embedding of Cycles in Arrangement Graphs, "IEEE Trans. Computers, vol. 42, no. 8, pp. 1008--1006, Aug. 1993.
S.Y. Hsieh, G.H. Chen, and C.W. Ho, "Fault-Free Hamiltonian Cycles in Faulty Arrangement Graphs, "IEEE Trans. Parallel and Distributed System, 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, "IEEE Trans. Computer, vol. 50, no. 9, pp. 960--971, Sept. 2001.
H.C. Hsu, T.K. Li, Member, IEEE, Jimmy J.M. Tan, and L.H. Hsu, "Fault Hamiltonicity and Fault Hamiltonian Connectivity of the Arrangement Graphs, "IEEE Transactions on Computers, vol. 53, no. 1, Jan. 2004.
W.T. Huang, J.M. Tan, C.N. Hung, and L.H. Hsu, :Fault-Tolerant Hamiltonicity of Twisted Cubes" J. Parallel and Distrbuted Computing, accepted, 2001.
S. Latifi, S.Q. Zheng, and N. Bagherzadeh, "Optimal Ring Embedding in Hypercubes with Faulty Links, "Proc. IEEE Symp. Fault-Tolerant Computing, vol. 42, pp. 178--184, 1992.
R.S. Lo and G.H. Chen, "Embedding Hamiltonian Paths in Fauly Arrangement Graphs with the Backtracking Method, "IEEE Trans. Parrallel and Distributed Systems, vol. 12, no. 2, pp. 209--221, Feb. 2001.
O. Ore, "Hamiltonian Connected Graph, "J. Math. Pures Applications, vol. 42, pp. 121--127, 1963.
R.A. Rowley and B. Boses, "Fault-Tolerant Ring Embedding in de Bruijn Networks, "IEEE Trans. Computers, vol. 42, no. 12, pp. 1480--1486, Dec. 1993.
Y. Saad and M.H. Schultz, "Topological Properties of Hypercubes, "IEEE Trans. Computers, vol. 37, no. 7, pp. 867--872, July 1988.
Y.C. Tseng, S.H. Chang, and J.P. Sheu, "Fault-Tolerant Ring Embedding in a Star Graph with Both Link and Node Failure, "IEEE Trans. Parallel and Distributed Systems, vol. 8, pp. 1185--1195, 1997.
D.B. West, Introduction to Graph Theory (Second Edition), Prentice Hall, Upper Saddle River, 2001.
校內：2008-09-06公開校外：2008-09-06公開