On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
344 | en_US |
dc.citation.issue |
2 | en_US |
dc.citation.spage |
328 | en_US |
dc.citation.volume |
27 | en_US |
dc.citation.woscount |
0 | |
dc.contributor.author |
Kung, Tzu-Liang | en_US |
dc.contributor.author |
Lin, Cheng-Kuan | en_US |
dc.contributor.author |
Hsu, Lih-Hsing | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.date.accessioned |
2014-12-08T15:34:28Z | |
dc.date.available |
2014-12-08T15:34:28Z | |
dc.date.issued |
2014-02-01 | en_US |
dc.description.abstract |
Hsieh and Yu (2007) first claimed that an injured n-dimensional hypercube Q (n) contains (n-1-f)-mutually independent fault-free Hamiltonian cycles, where fa parts per thousand currency signn-2 denotes the total number of permanent edge-faults in Q (n) for na parts per thousand yen4, and edge-faults can occur everywhere at random. Later, Kueng et al. (2009a) presented a formal proof to validate Hsieh and Yu's argument. This paper aims to improve this mentioned result by showing that up to (n-f)-mutually independent fault-free Hamiltonian cycles can be embedded under the same condition. Let F denote the set of f faulty edges. If all faulty edges happen to be incident with an identical vertex s, i.e., the minimum degree of the survival graph Q (n) -F is equal to n-f, then Q (n) -F contains at most (n-f)-mutually independent Hamiltonian cycles starting from s. From such a point of view, the presented result is optimal. Thus, not only does our improvement increase the number of mutually independent fault-free Hamiltonian cycles by one, but also the optimality can be achieved. | en_US |
dc.identifier.doi |
10.1007/s10878-012-9528-1 | en_US |
dc.identifier.issn |
1382-6905 | en_US |
dc.identifier.journal |
JOURNAL OF COMBINATORIAL OPTIMIZATION | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1007/s10878-012-9528-1 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/23581 | |
dc.identifier.wosnumber |
WOS:000330590400009 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Interconnection network | en_US |
dc.subject |
Graph | en_US |
dc.subject |
Hypercube | en_US |
dc.subject |
Fault tolerance | en_US |
dc.subject |
Hamiltonian cycle | en_US |
dc.title |
On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube | en_US |
dc.type |
Article | en_US |
檔案
- 000330590400009.pdf (773.4 KB, Adobe PDF)
所屬典藏: 期刊論文
引用此條目
Kung, T.-L., Lin, C.-K., & Hsu, L.-H. (2014). On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube. JOURNAL OF COMBINATORIAL OPTIMIZATION, 27(2), 328–344. https://doi.org/10.1007/s10878-012-9528-1
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/23581