Super fault-tolerant hamiltonicity of product networks

Sun-Yuan Hsieh, Tsong Jie Lin

研究成果: Conference contribution

4 引文 斯高帕斯(Scopus)

摘要

A graph G is called k-fault Hamiltonian (resp. Hamiltonian-connected) if after deleting at most k vertices and/or edges from G, the resulting graph remains Hamiltonian (resp. Hamiltonian-connected). Let δ(G) be the minimum degree of G. Given a (δ(G) - 2)-fault Hamiltonian/ (δ(G) - 3)-fault Hamiltonian-connected graph G and a (δ(H) - 2)-fault Hamiltonian/ (δ(H)-3)-fault Hamiltonian-connected graph H, we show that the Cartesian product network G x H is (δ(G)+δ(H)-2)-fault Hamiltonian and (δ(G)+δ(H)-3)-fault Hamiltonian-connected. We then apply our result to determine the fault-tolerant hamiltonicity and Hamiltonian-connectivity of two multiprocessor systems, namely the generalized hypercube and the nearest neighbor mesh hypercube, both of which belong to Cartesian product networks. We also demonstrate that our results are worst-case optimal with respect to the number of faults tolerated.

原文English
主出版物標題Proceedings - International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010
頁面236-243
頁數8
DOIs
出版狀態Published - 2010 十二月 1
事件International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010 - Taipei, Taiwan
持續時間: 2010 九月 62010 九月 9

出版系列

名字Proceedings - International Symposium on Parallel and Distributed Processing with Applications, ISPA 2010

Other

OtherInternational Symposium on Parallel and Distributed Processing with Applications, ISPA 2010
國家/地區Taiwan
城市Taipei
期間10-09-0610-09-09

All Science Journal Classification (ASJC) codes

  • 計算機理論與數學
  • 電腦科學應用

指紋

深入研究「Super fault-tolerant hamiltonicity of product networks」主題。共同形成了獨特的指紋。

引用此