進階搜尋

學院別 > 成功大學 > 電機資訊學院 > 資訊工程學系

下載電子全文  
系統識別號 U0026-1507201113312100
論文名稱(中文) 摺疊式超立方體之超連通度和條件偵錯度研究
論文名稱(英文) Extra Connectivity and Conditional Diagnosability of Folded Hypercubes
校院名稱 成功大學
系所名稱(中) 資訊工程學系碩博士班
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 99
學期 2
出版年 100
研究生(中文) 蔡政諺
研究生(英文) Cheng-Yen Tsai
學號 p76981196
學位類別 碩士
語文別 英文
論文頁數 82頁
口試委員 指導教授-謝孫源
口試委員-陳維美
口試委員-黃冠寰
口試委員-賴泳伶
口試委員-阮夙姿
中文關鍵字 互聯網路  連通度  邊連通度  超連通度  超邊連通度  偵錯度  強偵錯度  條件偵錯度  比較診斷模式  MM*模式  容錯  可靠度  摺疊式超立方體 
英文關鍵字 Interconnection networks  connectivity  edge connectivity  extra connectivity  extra edge connectivity  diagnosability  strong diagnosability  conditional diagnosability  comparison diagnosis model  MM* model  fault-tolerance  reliability  folded hypercubes 
學科別分類
中文摘要 給定一個圖G以及一個非負整數g，G的g-超連通度(g-extra connectivity)是: 能使G不連通(disconnected)以及所有剩餘的連通分量(component)均大於g個頂點所需刪除的最小頂點集合的元素個數; G的g-超邊連通度(g-extra edge connectivity)是: 能使G不連通以及所有剩餘的連通分量均大於g個頂點所需刪除的最小邊集合的元素個數。在本篇論文中，我們首先證明: 一個n維的摺疊式超立方體(folded hypercube)的3-超連通度是4n - 5(當n ≥ 6)以及一個n維的摺疊式超立方體的3-超邊連通度是4n - 4(當n ≥ 4)。

強偵錯度(strong diagnosability)和條件偵錯度(conditional diagnosability)是衡量系統偵錯度(diagnosability)的兩個新的基準-藉由增加一個額外的限制條件: 在一個系統中，任一個錯集(faulty set)不能含括任一個頂點的所有鄰居(neighbor)。在比較診斷模式(comparison diagnosis model)下，本篇論文提出了一些有用的充分條件用於決定一個系統G的強偵錯度ts(G)和條件偵錯度tc(G)。藉由應用這些結果在一個n維的摺疊式超立方體FQn上，我們證明了ts(FQn) = n + 1(當n ≥ 5)以及tc(FQn) = 3n - 2(當n ≥ 5)。再者，我們也證明tc(FQ3) = 3和tc(FQ4) = 7。

當摺疊式超立方體被使用當作大規模平行處理系統(large-scale parallel processing system)的基本模型時，以上的結果可以提供更精確的測量對於系統的可靠度(reliability)以及容錯能力(fault-tolerance)。
英文摘要 Given a graph G and a non-negative integer g, the g-extra connectivity (resp. g-extra edge connectivity) of G is the minimum cardinality of a set of vertices (resp. edges) in G, if exists, whose deletion disconnects G and every remaining component has more than g vertices. In this thesis, we first show that the 3-extra connectivity (resp. 3-extra edge connectivity) of the n-dimensional folded hypercube is 4n − 5 for n ≥ 6 (resp. 4n − 4 for n ≥ 4).

The strong diagnosability and conditional diagnosability are two novel measures of diagnosability by adding an additional restriction that any faulty set cannot contain all the neighbors of any node in a system. Under the comparison diagnosis model, this thesis proposes some useful sufficient conditions for determining the strong diagnosability ts(G) and the conditional diagnosability tc(G) of a system G, respectively. By applying these results to an n-dimensional folded hypercube FQn, we show that ts(FQn) = n + 1 for n ≥ 5 and tc(FQn) = 3n − 2 for n ≥ 5. Moreover, we also show that tc(FQ3) = 3 and tc(FQ4) = 7.

When folded hypercubes are used as fundamental models for large-scale parallel processing systems, these results can provide more accurate measurements for reliability and fault tolerance of the system.
論文目次 1 Introduction 1
1.1 The Folded Hypercube 1
1.2 Fault Tolerance 2
1.3 Fault Diagnosis 4

2 Preliminaries 6
2.1 Basic Definitions and Notations 6
2.2 Comparison Diagnosis Model 9
2.3 Diagnosability of Systems 10

3 Properties of Folded Hypercubes 12
3.1 Basic Properties 12
3.2 Properties of the Common Neighborhood 13

4 3-Extra Connectivity of Folded Hypercubes 28

5 3-Extra Edge Connectivity of Folded Hypercubes 40

6 Strong Diagnosability of Folded Hypercubes 54

7 Conditional Diagnosability of Folded Hypercubes 57

8 Conclusion 65

Bibliography 67

Appendix A 76
Appendix B 78
Appendix C 81
參考文獻 [1] J. R. Armstrong and F. G. Gray, “Fault diagnosis in a boolean n cube array of multiprocessors,” IEEE Transactions on Computers, vol. 30, issue 8, pp. 587–590, 1981.

[2] C. Balbuena, “Extraconnectivity of s-geodetic digraphs and graphs,” Discrete Mathematics, vol. 195, pp. 39–52, 1999.

[3] C. Balbuena, A. Carmona, J. F`abrega, and M. A. Fiol, “Extraconnectivity of graphs with large minimum degree and girth,” Discrete Mathematics, vol. 167-168, pp. 85–100, 1997.

[4] C. Balbuena, M. Cera, A. Di´anez, P. Garc´ıa-V´azquez, and X. Marcote, “Sufficient conditions for λ′-optimality of graphs with small conditional diameter,” Information Processing Letters, vol. 95, issue 4, pp. 429–434, 2005.

[5] C. Balbuena, M. Cera, A. Di´anez, P. Garc´ıa-V´azquez, and X. Marcote, “On the edge-connectivity and restricted edge-connectivity of a product of graphs,” Discrete Applied Mathematics, vol. 155, issue 18, pp. 2444–2455, 2007.

[6] C. Balbuena, M. Cera, A. Di´anez, P. Garc´ıa-V´azquez, and X. Marcote, “On the restricted connectivity and superconnectivity in graphs with given girth,” Discrete Mathematics, vol. 307, issue 6, pp. 659–667, 2007.

[7] C. Balbuena, M. Cera, A. Di´anez, P. Garc´ıa-V´azquez, and X. Marcote, “Diametergirth sufficient conditions for optimal extraconnectivity in graphs,” Discrete Mathematics, vol. 308, issue 16, pp. 3526–3536, 2008.

[8] C. Balbuena, D. Gonz´alez-Moreno, and X. Marcote, “On the 3-restricted edge connectivity of permutation graphs,” Discrete Applied Mathematics, vol. 157, issue 7, pp. 1586–1591, 2009.

[9] G. Y. Chang, G. J. Chang, and G. H. Chen, “Diagnosabilities of regular networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 16, issue 4, pp. 314–323, 2005.

[10] N. W. Chang and S. Y. Hsieh, “Conditional diagnosability of augmented cubes under the PMC model,” IEEE Transactions on Dependable and Secure Computing, http://doi.ieeecomputersociety.org/10.1109/TDSC.2010.59.

[11] Y. C. Chen and J. J. M. Tan, “Restricted connectivity for three families of interconnection networks,” Applied Mathematics and Computation, vol. 188, issue 2, pp. 1848–1855, 2007.

[12] E. P. Duarte JR, R. P. Ziwich, and L. C. P. Albini, “A Survey of Comparison-Based System-Level Diagnosis,” ACM Computing Surveys, vol. 43, no. 3, article 22, pp. 1–56, 2011.

[13] A. El-Amawy and S. Latifi, “Properties and performance of folded hypercubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 2, issue 1, pp. 31–42, 1991.

[14] A. H. Esfahanian, “Generalized measures of fault tolerance with application to n-cube networks,” IEEE Transactions on Computers, vol. 38, no. 11, pp. 1586–1591, 1989.

[15] A. H. Esfahanian and S. L. Hakimi, “On computing a conditional edge-connectivity of a graph,” Information Processing Letters, vol. 27, issue 4, pp. 195–199, 1988.

[16] J. F`abrega and M. A. Fiol, “Extraconnectivity of graphs with large girth,” Discrete Mathematics, vol. 127, pp. 163–170, 1994.

[17] J. F`abrega and M. A. Fiol, “On the extraconnectivity of graphs ,” Discrete Mathematics, vol. 155, pp. 49–57, 1996.

[18] J. Fan, “Diagnosability of crossed cubes under the two strategies,” Chinese Journal of Computers, vol. 21, issue 5, pp. 456–462, 1998.

[19] J. Fan, “Diagnosability of the M¨obius cubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 9, issue 9, pp. 923–928, 1998.

[20] H. Fugiwara and K. Kinoshita, “On the computational complexity of system diagnosis,” IEEE Transactions on Computers, vol. 27, issue 10, pp. 881–885, 1978.

[21] A. Ghafoor, “A class of fault-tolerant multiprocessor networks,” IEEE Transactions on Reliability, vol. 38, issue 1, pp. 5–15, 1989.

[22] A. Ghafoor, “Partitioning of even networks for improved diagnosability,” IEEE Transactions on Reliability, vol. 39, issue 3, pp. 281–286, 1990.

[23] S. L. Hakimi and A. T. Amin, “Characterization of connection assignment of diagnosable systems,” IEEE Transactions on Computers, vol. 23, pp. 86–88, 1974.

[24] F. Harary, “Conditional connectivity,” Networks, vol. 13, issue 3, pp. 347–357, 1983.

[25] W. S. Hong and S. Y. Hsieh, “Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model,” IEEE Transactions on Reliability, accepted.

[26] S. Y. Hsieh and Y. S. Chen, “Strongly diagnosable product networks under the comparison diagnosis model,” IEEE Transactions on Computers, vol. 57, issue 6, pp. 721–732, 2008.

[27] S. Y. Hsieh and Y. S. Chen, “Strongly diagnosable systems under the comparison diagnosis model,” IEEE Transactions on Computers, vol. 57, issue 12, pp. 1720–1725, 2008.

[28] S. Y. Hsieh and T. Y. Chuang, “The strong diagnosability of regular networks and product networks under the PMC model,” IEEE Transactions on Parallel and Distributed Systems, vol. 20, issue 3, pp. 367–378, 2009.

[29] S. Y. Hsieh and C. N. Kuo, “Hamiltonian-connectivity and strongly Hamiltonianlaceability of folded hypercube,” Computers and Mathematics with Applications, vol. 53, pp. 1040–1044, 2007.

[30] G. H. Hsu, C. F. Chiang, L. M. Shih, L. H. Hsu, and J. J. M. Tan, “Conditional diagnosability of hypercubes under the comparison diagnosis model,” Journal of Systems Architecture, vol. 55, issue 2, pp. 140–146, 2009.

[31] G. H. Hsu and J. J. M. Tan, “Conditional diagnosability of the BC networks under the comparison diagnosis model,” International Computer Symposium, vol. 1, pp. 269–274, 2008.

[32] A. Kavianpour, “Sequential diagnosability of star graphs,” Computers and Electrical Engineering, vol. 22, issue 1, pp. 37–44, 1996.

[33] A. Kavianpour and K. H. Kim, “Diagnosability of hypercubes under the pessimistic one-step diagnosis strategy,” IEEE Transactions on Computers, vol. 40, issue 2, pp. 232–237, 1991.

[34] A. Kavianpour and K. H. Kim, “A comparative evaluation of four basic system-level diagnosis strategies for hypercubes,” IEEE Transactions on Reliability, vol. 41, issue 1, pp. 26–37, 1992.

[35] C. N. Lai and G. H. Chen, “Strong Rabin numbers of folded hypercubes,” Theoretical Computer Science, vol. 341, issue 1–3, pp. 196–215, 2005.

[36] C. N. Lai, G. H. Chen, and D. R. Duh, “Constructing one-to-many disjoint paths in folded hypercubes,” IEEE Transactions on Computers, vol. 51, issue 1, pp. 33–45, 2002.

[37] P. L. Lai, J. M. Tan, C. P. Chang, and L. H. Hsu, “Conditional diagnosability measures for large multiprocessor systems,” IEEE Transactions on Computers, vol. 54, issue 2, pp. 165–175, 2005.

[38] S. Latifi, M. Hegde, and M. Naraghi-Pour, “Conditional connectivity measures for large multiprocessor systems,” IEEE Transactions on Computers, vol. 43, no. 2, pp. 218–222, 1994.

[39] C. W. Lee and S. Y. Hsieh, “Determining the diagnosability of (1,2)-matching composition networks and its applications,” IEEE Transactions on Dependable and Secure Computing, vol. 8, issue 3, pp. 353–362, 2011.

[40] C. W. Lee and S. Y. Hsieh, “Diagnosability of two-matching composition networks under the MM* model,” IEEE Transactions on Dependable and Secure Computing, vol. 8, issue 2, pp. 246–255, 2011.

[41] C. K. Lin, J. J. M. Tan, L. H. Hsu, E. Cheng, and L. Lipt´ak, “Conditional diagnosability of Cayley graphs generated by transposition trees,” Journal of Interconnection Networks, vol. 9, issue 1-2, pp. 83–97, 2008.

[42] S. W. Lin and S. Y. Wang, “Super p-restricted edge connectivity of line graphs,” Information Sciences, vol. 179, issue 18, pp. 3122–3126, 2009.

[43] M. L¨u, G. L. Chen, and X. R. Xu, “On super edge-connectivity of product graphs,” Applied Mathematics and Computation, vol. 207, issue 2, pp. 300–306, 2009.

[44] M. J. Ma, G. Z. Liu, and J. M. Xu, “The super connectivity of augmented cubes,” Information Processing Letters, vol. 106, issue 2, pp. 59–63, 2008.

[45] M. J. Ma, J. M. Xu, and Z. Z. Du, “Edge-fault-tolerant hamiltonicity of folded hypercubes,” Journal of University of Science and Technology of China, vol. 36, issue 3, pp. 244–248, 2006.

[46] J. Maeng and M. Malek, “A comparison connection assignment for self-diagnosis of multiprocessors systems,” in Proceedings of the 11th International Symposium on Fault-Tolerant Computing, pp. 173–175, 1981.

[47] M. Malek, “A comparison connection assignment for diagnosis of multiprocessors systems,” in Proceedings of the 7th International Symposium on Computer Architecture, pp. 31–36, 1980.

[48] J. X. Meng and Y. H. Ji, “On a kind of restricted edge connectivity of graphs,” Discrete Applied Mathematics, vol. 117, pp. 183–193, 2002.

[49] J. P. Ou, X. H. Cheng, and J. C.Wu, “On 3-restricted edge connectivity of undirected binary Kautz graphs,” Discrete Mathematics, vol. 309, issue 4, pp. 629–638, 2009.

[50] F. P. Preparata, G. Metze, and R.T. Chien, “On the connection assignment problem of diagnosis systems,” IEEE Transactions on Electronic Computers, vol. 16, issue 12, pp. 848–854, 1967.

[51] A. Sengupta and A. Dahbura, “On self-diagnosable multiprocessor systems: diagnosis by the comparison approach,” IEEE Transactions on Computers, vol. 41, issue 11, pp. 1386–1396, 1992.

[52] J. J. Sheu, W. T. Huang, and C. H. Chen, “Strong diagnosability of regular networks under the comparison model,” Information Processing Letters, vol. 106, pp. 19–25, 2008.

[53] L. Volkmann, “Restricted arc-connectivity of digraphs,” Information Processing Letters, vol. 103, issue 6, pp. 234–239, 2007.

[54] M. Wan and Z. Zhang, “A kind of conditional vertex connectivity of star graphs,” Applied Mathematics Letters, vol. 22, issue 2, pp. 264–267, 2009.

[55] D. Wang, “Diagnosability of enhanced hypercubes,” IEEE Transactions on Computers, vol. 43, issue 9, pp. 1054–1061, 1994.

[56] D. Wang, “Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model,” IEEE Transactions on Computers, vol. 48, issue 12, pp. 1369–1374, 1999.

[57] Y. Q.Wang, “Super restricted edge-connectivity of vertex-transitive graphs,” Discrete Mathematics, vol. 289, pp. 199–205, 2004.

[58] M. Wang and Q. Li,“Conditional edge connectivity properties, reliability comparisons and transitivity of graphs,” Discrete Mathematics, vol. 258, pp. 205–214, 2002.

[59] S. Y. Wang, S. W. Lin, and C. F. Li, “Sufficient conditions for super k-restricted edge connectivity in graphs of diameter 2,” Discrete Mathematics, vol. 309, issue 4, pp. 908-919, 2009.

[60] S. Y. Wang, J. Yuan, and A. X. Liu, “k-restricted edge connectivity for some interconnection networks,” Applied Mathematics and Computation, vol. 201, issues 1-2, pp. 587–596, 2008.

[61] D. B. West, Introduction to Graph Theory, Prentice Hall Publishers, 2001.

[62] H. Whitney, “Congruent graphs and the connectivity of graphs,” Amer. J. Math., vol. 54, pp. 150–168, 1932.

[63] J. M. Xu, Topological structure and analysis of interconnection networks, Kluwer Academic Publishers, 2001.

[64] J. M. Xu, M. L¨u, M. J. Ma, and A. Hellwig, “Super connectivity of line graphs,” Information Processing Letters, vol. 94, issue 4, pp. 191–195, 2005.

[65] M. Xu, K. Thulasiraman, and X. D. Hu,“Conditional diagnosability of matching composition networks under the PMC model,” IEEE Transactions on Circuits and Systems II, vol. 56, issue 11, pp. 875–879, 2009.

[66] J. M. Xu, J. W. Wang, and W. W. Wang, “On super and restricted connectivity of some interconnection networks,” Ars Combinatoria, vol. 94, 2010.

[67] J. M. Xu, Q. Zhu, X. M. Hou, and T. Zhou, “On restricted connectivity and extra connectivity of hypercubes and folded hypercubes,” J. of Shanghai Jiaotong Univ. (sci), vol. 10, issue 2, pp. 203–207, 2005.

[68] J. M. Xu, Q. Zhu, and M. Xu, “Fault-tolerant analysis of a class of networks,” Information Processing Letters, vol. 103, issue 6, pp. 222–226, 2007.

[69] W. H. Yang and J. X. Meng, “Extraconnectivity of hypercubes,” Applied Mathematics Letters, vol. 22, issue 6, pp. 887–891, 2009.

[70] Z. Zhang, “Sufficient conditions for restricted-edge-connectivity to be optimal,” Discrete Mathematics, vol. 307, issue 22, pp. 2891–2899, 2007.

[71] Z. Zhang, “Extra edge connectivity and isoperimetric edge connectivity,” Discrete Mathematics, vol. 308, issue 20, pp. 4560–4569, 2008.

[72] J. Zhao, F. J. Meyer, N. Park, and F. Lombardi, “Sequential diagnosis of processor array systems,” IEEE Transactions on Reliability, vol. 53, issue 4, pp. 487–498, 2004.

[73] S. Zhou, “The conditional diagnosability of M¨obius cubes under the comparison model,” Proceedings of the 2009 IEEE International Conference on Information and Automation, pp. 96–100, 2009.

[74] S. Zhou, “The conditional diagnosability of locally twisted cubes,” Proceedings of 2009 4th International Conference on Computer Science and Education, pp. 221–226, 2009.

[75] S. Zhou, “The conditional diagnosability of twisted cubes under the comparison model,” 2009 IEEE International Symposium on Parallel and Distributed Processing with Applications, pp. 696–701, 2009.

[76] Q. Zhu, “On conditional diagnosability and reliability of the BC networks,” The Journal of Supercomputing, vol. 45, issue 2, pp. 173–184, 2008.

[77] Q. Zhu, S. Y. Liu, and M. Xu, “On conditional diagnosability of the folded hypercubes,” Information Sciences, vol. 178, issue 4, pp. 1069–1077, 2008.

[78] Q. Zhu and J. M. Xu, “On restricted edge connectivity and extra edge connectivity of hypercubes and folded hypercubes,” J. University of Science and Technology of China, vol. 36, issue 3, pp. 246–253, 2006.

[79] Q. Zhu, J. M. Xu, X. M. Hou, and M. Xu, “On reliability of the folded hypercubes,” Information Sciences, vol. 177, issue 8, pp. 1782–1788, 2007.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務，於2012-07-21起公開。
  • 同意授權校外瀏覽/列印電子全文服務，於2013-07-21起公開。
    		•

    如您有疑問，請聯絡圖書館
    聯絡電話：(06)2757575#65773
    聯絡E-mail：etds@email.ncku.edu.tw