Copyright © 2007 The Institute of Electronics, Information and Communication Engineers
Regular Section -- Papers -- Algorithm Theory |
Hamiltonian Cycles and Hamiltonian Paths in Faulty Burnt Pancake Graphs
1 The author is with the Graduate School of Engineering, Tokyo University of Agriculture and Technology, Koganei-shi, 184-8588 Japan. E-mail: k1kaneko{at}cc.tuat.ac.jp
Recently, research on parallel processing systems is very active, and many complex topologies have been proposed. A burnt pancake graph is one such topology. In this paper, we prove that a faulty burnt pancake graph with degree n has a fault-free Hamiltonian cycle if the number of the faulty elements is n–2 or less, and it has a fault-free Hamiltonian path between any pair of nonfaulty nodes if the number of the faulty elements is n – 3 or less.
Key Words: signed permutation, interconnection network, routing algorithm, parallel processing
Manuscript received October 27, 2006.
References
[1] S.B. Akers and B. Krishnamurthy, "A group-theoretic model for symmetric interconnection networks," IEEE Trans. Comput., vol.38, no.4, pp.555–566, 1989.
[2] S.G. Akl, K. Qiu, and I. Stojmenovi
, "Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry," Networks, vol.23, no.4, pp.215–226, July 1993.
[3] M.Y. Chan and S.J. Lee, "On the existence of Hamiltonian circuits in faulty hypercubes," SIAM J. Discrete Math., vol.4, no.4, pp.511–527, 1991.
[4] P.F. Corbett, "Rotator graphs: An efficient topology for point-to-point multiprocessor networks," IEEE Trans. Parallel Distrib. Syst., vol.3, no.5, pp.622–626, May 1992.
[5] M. Dietzfelbinger, S. Madhavapeddy, and I.H. Sudborough, "Three disjoint path paradigms in star networks," Proc. IEEE Symposium on Parallel and Distributed Processing, pp.400–406, 1991.
[6] J. Fan, "Hamiltonian-connectivity and cycle-embedding of the Möbius cubes," Inf. Process. Lett., vol.82, no.2, pp.113–117, 2002.
[7] L. Gardner, Z. Miller, D. Pritikin, and I.H. Sudborough, "Embedding hypercubes into pancake, cycle prefix and substring reversal networks," Proc. 28th Annual Hawaii International Conference on System Science, pp.537–545, 1995.
[8] L. Gargano, U. Vaccaro, and A. Vozella:, "Fault tolerant routing in the star and pancake interconnection networks," Inf. Process. Lett., vol.45, no.6, pp.315–320, 1993.
[9] W.H. Gates and C.H. Papadimitriou, "Bounds for sorting by prefix reversal," Discrete Math., vol.27, pp.47–57, 1979.
[10] Q.P. Gu and S. Peng, "Node-to-set disjoint paths problem in star graphs," Inf. Process. Lett., vol.62, no.4, pp.201–207, April 1997.
[11] Q.P. Gu, S. Peng, and I.H. Sudborough, "A 2-approximation algorithm for genome rearrangements by reversals and transpositions," Theor. Comput. Sci., vol.210, no.2, pp.327–339, 1999.
[12] Y. Hamada, F. Bao, A. Mei, and Y. Igarashi, "Nonadaptive fault-tolerant file transmission in rotator graphs," IEICE Trans. Fundamentals, vol.E79-A, no.4, pp.477–482, April 1996.
[13] S.Y. Hsieh, G.H. Chen, and C.W. Ho, "Hamiltonian-laceability of star graphs," Proc. International Symposium on Parallel Architectures, Algorithms, and Networks, pp.112–117, 1997.
[14] S.Y. Hsieh, G.H. Chen, and C.W. Ho, "Fault-free Hamiltonian cycles in faulty arrangement graphs," IEEE Trans. Parallel Distrib. Syst., vol.10, no.3, pp.223–237, 1999.
[15] C.N. Hung, H.C. Hsu, K.Y. Liang, and L.H. Hsu, "Ring embedding in faulty pancake graphs," Inf. Process. Lett., vol.86, no.5, pp.271–275, June 2003.
[16] C.N. Hung, K.Y. Liang, and L.H. Hsu, "Embedding Hamiltonian paths and Hamiltonian cycles in faulty pancake graphs," Proc. International Symposium on Parallel Architectures, Algorithms and Networks, pp.179–184, March 2002.
[17] K. Kaneko, "An algorithm for node-to-set disjoint paths problem in burnt pancake graphs," IEICE Trans. Inf. & Syst., vol.E86-D, no.12, pp.2588–2594, Dec. 2003.
[18] M. Nigam, S. Sahni, and B. Krishnamurthy, "Embedding Hamiltonians and hypercubes in star interconnection networks," Proc. International Conference on Parallel Processing, pp.340–343, 1990.
[19] M.C. Yang, T.K. Li, J.J.M. Tan, and L.H. Hsu, "Fault-tolerant pancyclicity of the Möbius cubes," IEICE Trans. Fundamentals, vol.E88-A, no.1, pp.346–352, Jan. 2005.[Abstract]
CiteULike 
Connotea 
Del.icio.us What's this?
| ||||||||||||||||||||||||||||||||||||||||||||||||