標題: On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube
作者: Kung, Tzu-Liang
Lin, Cheng-Kuan
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
關鍵字: Interconnection network;Graph;Hypercube;Fault tolerance;Hamiltonian cycle
公開日期: 1-Feb-2014
摘要: 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.
URI: http://dx.doi.org/10.1007/s10878-012-9528-1
http://hdl.handle.net/11536/23581
ISSN: 1382-6905
DOI: 10.1007/s10878-012-9528-1
期刊: JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume: 27
Issue: 2
起始頁: 328
結束頁: 344
Appears in Collections:Articles


Files in This Item:

  1. 000330590400009.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.