設計互連網路的架構是在平行處理和分散式系統中最重要而且不可或缺的一個部份。可是在互連網路的拓樸與設計上存在著許多相互抵觸的要求，因此要設計一個完美的互連網 路來符合各方面的要求而且都是最佳化的狀況幾乎是不可能的事。而超立方體(hypercube)網路在平行處理和分散式系統中擁有許多優異的性質，例如：遞迴的結構，規則性 (regular)，對稱性(symmetric)，分支度小，和強大的連接性。除了上述所談到的架構之外，一種被擴充的超 立方體，稱作摺疊式超立方體也在學術上被廣泛的研究，它是原本的超立方體再加上最遠任意兩個點的邊，也就是說，當兩個點編號互補時就會有邊存在。而且摺疊式超立方體也已經被證明出，在許多方面的測量上能夠改進超立方體的系統效能。
路徑和迴路是分散式計算中最基本的兩種網路結構，它們適合應用於需要較少通訊花費的簡單演算法上面。除此之外，它們也適合應用在網路架構上的控制或資料流架構的分散式計算。而且路徑也可以實際應用在解決彈性生產系統的線上最佳化問題。由於這些實際的應用，促使我們研究網路上許多路徑和迴路的嵌入問題。
在此篇論文中，我們的研究方向著落在超立方體和摺疊式超立方體上路徑和環路的容錯嵌入問題。

Design of interconnection networks is an important integral part of the parallel processing or distributed system. There exists mutually con°icting requirements in designed and topology of interconnection networks. It becomes almost impossible for us to design a network which is optimum in all aspects. The hypercube has several excellent proper-
ties such as recursive structure, regularity, symmetry, small diameter, low degree, and much small edge complexity, which are very important for designing massively parallel
or distributed systems. Furthermore, one variant that has been the focus of great deal of research is the folded hypercube, which is an extension of the hypercube, constructed by adding an edge to every pair of nodes that are the farthest apart, i.e., two nodes with complementary addresses. The folded hypercube has been shown to be able to improve the system's performance over a regular hypercube in many measurements. Paths and cycles, which are two of the most fundamental networks for parallel and distributed computation, are suitable for designing simple algorithms with low commu-nication costs. Paths and cycles can also be used as control/data flow structures for
distributed computation in arbitrary networks. An application of paths to a practical problem was encountered in the on-line optimization of a complex flexible manufacturing system. These applications motivate us to embedding paths and cycles in networks.
In this dissertation, we consider fault-tolerant path or cycle embedding problems in hypercubes and in folded hypercubes.

[1] A. El-Amawy and S. Latif, "Properties and performance of folded hypercubes," IEEE Transactions on Parallel and Distributed Systems, vol. 2, no. 1, pp. 31-42, 1991.
[2] S. G. Akl, Parallel Computation: Models and Methods, Prentice Hall, 1997.
[3] S. B. Akers, D. Horel, and B. Krishnamurthy, "The star graph: an attractive alternative to the n-cube," Proceedings of the International Conference on Parallel
Processing , pp. 393{400, 1987.
[4] N. Ascheuer, "Hamiltonian path problems in the on-line optimization of flexible manufacturing systems," PH.D. Thesis, University of Technology, Berlin, Germany,
1995.
[5] Y. A. Ashir and I. A. Stewart, "Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes," SIAM Journal on Discrete Mathematics, vol. 15, pp. 317-328, 2002.
[6] Avizienis, A., Fault tolerant computing- an pverview. IEEE Transations on Computers, vol. 4, pp. 5-8, 1971.
[7] J. C. Bermond, Ed., "Interconnection networks," a special issue of Discrete Applied Mathematics, vol. 37-38, 1992.
[8] L. Bhuyan and D. P. Agrawal, "Generalised hypercubes and hyperbus structure for a computer network," IEEE Transactions on Computers, c. 33, pp. 323-333, 1984.
[9] M. Y. Chan and S. J. Lee. "Distributed fault-tolerant embeddings of rings in hypercubes," Jurnal of Parallel and Distributed Computing, 11: 63-71, 1991.
[10] J. M. Chang and S. J. Yang. "On the existence of Hamiltonian circuits in faulty hypercubes," SIAM Journal on Discrete Mathematics, 4(4):511-527, 1991.
[11] J. Chang, J. Yang, and Y. Chang, "Panconnectivity, fault-Tolorant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs", Networks, 44(4): 302-310, 2004.
[12] M. S. Chen and K. G. Shin, "Processor allocation in an N-cube multiprocessor using gray codes," IEEE Transactions on Computers, vol. 36, issue 12, pp. 1396-1407, 1987.
[13] S. A. Choudum and V. Sunitha, "Augmented cubes," Networks, vol. 40, no. 2, pp. 71-84, 2002.
[14] D. Wang, "Embedding Hamiltonian cycles into folded hypercubes with faulty links," Journal of Parallel and Distributed Computing, vol. 61, no. 4, pp. 545-564, 2001.
[15] K. Efe, "The crossed cube architecture for parallel computation," IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 5, pp. 513-524, 1992.
[16] Esfahanian, A. H., and Hakimi, S. L., Fault-tolerant routing in the Bruijn communication networks. IEEE Transations on Computers,34 (9): 777-788, 1985.
[17] A. H. Esfahanian, L. M. Ni, and B. E. Sagan, "The twisted N-cube with application to miltiprocessing," IEEE Transactions on Computers, vol. 40, no. 1, pp. 88-93,
1991.
[18] J. S. Fu, "Fault-tolerant cycle embedding in the hypercube," Parallel Computing, vol. 29, issue 6, pp. 821-832, 2003.
[19] J. S. Fu, "Fault-tolerant cycle embedding in hierarchial cubic networks," Networks, 43(1): 28-38, 2004.
[20] J. S. Fu, "Longest fault-free paths in hypercubes with vertex faults," Information Science, vol. 176, pp. 759-771, 2006.
[21] J. S. Fu, "Conditional fault-tolerant hamiltonicity of star graphs," Parallel Computing, vol. 33, pp. 488-496, 2007.
[22] J. S. Fu, "Fault-free cycles in folded hypercubes with more faulty elements," Information Processing Letters, vol. 108, issue 5, pp. 261-163, 2008.
[23] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, CA, 1979.
[24] F. Harary, Conditional connectivity. Networks, 13:347-357, 1983.
[25] D. F. Hsu, "Interconnection networks and algorithms," a special issue of Networks, vol. 23, no. 4, 1993.
[26] S. Y. Hsieh, G. H. Chen, and C. W. Ho, "Hamiltonian-laceability of star graphs," Networks, vol. 36, no. 4, pp. 225-232, 2000.
[27] S. Y. Hsieh, "Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges," Parallel Computing, vol. 32, issue 1, pp. 84-91, 2006.
[28] S. Y. Hsieh and C. H. Chen, Pancyclicity on Mobius cubes with maximal edge faults, Parallel Computing, 30 (2004), 407-421.
[29] S. Y. Hsieh and G. H. Chen, and C. W. Ho. Fault-free hamiltonian cycles in faulty arrangemenet graphs. IEEE Transations on Parallel and Distributed Systems, 10(3):
223-237, 1999.
[30] S. Y. Hsieh and G. H. Chen, and C. W. Ho. Longest fault-free paths in star graphs with edge faults. IEEE Transations on Computers, 50(9): 960-971, 2001.
[31] S. Y. Hsieh, and T. H. Shen, "Edge-Bipancyclicity of a Hypercube with faulty Vertices and Edges," Discrete Applied Mathematics, vol. 156, issue 10, pp. 1802-1808, 2008.
[32] S. Y. Hsieh, "A note on cycle embedding in folded hypercubes with faulty elements," Information Processing Letters, vol. 108, issue 2, pp. 81, 2008.
[33] S. Y. Hsieh, "Some edge-fault-tolerant properties of the folded hypercube," Networks, vol. 51, no. 2, pp. 92-101, 2008.
[34] S. Y. Hsieh and C. Y. Wu, "Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults," Journal of Combinatorial Optimization, in Press.
[35] H. C. Hsu, L. C. Chiang, J. J. M. Tan, and L. H. Hsu, "Fault hamiltonicity of augmented cubes," Parallel Computing, 31(1): 131-145, 2005.
[36] H. C. Hsu, T. K. Li, J. J. M. Tan, and L. H. Hsu, "Fault hamiltonicity and fault hamiltonian connectivity of the arrangment graphs," IEEE Transactions on Computers, 53(1): 39-52, 2004.
[37] H. S. Hung, G. H. Chen, and J. S. Fu, "Fault-free Hamiltonian cycles in crossed cubes with conditional link faults," Information Sciences, vol. 177 no. 24, pp. 5664-5674,2007.
[38] S. Latif, S. Q. Zheng, and N. Bagherzadeh, "Optimal ring embedding in hypercubes with faulty links," in: Proceedings of the Twenty-Second International Symposium
on Fault-Tolerant Computing, pp. 178-184, 1992.
[39] S. Lakshmivarahan, J. S. Jwo, and S. K. Dhall, "Symmetry in interconnection networks based on Caley graphs of permutation groups: A survey," Parallel Computing,
vol. 19, pp. 1-47, 1993.
[40] F. T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays¢ Trees¢ Hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[41] Y. R. Leu and S. Y. Kuo, "Distributed Fault-tolerant ring embedding and reconfiguration in hypercubes." IEEE Transation on ComputersI, 48(1): 81-88, 1999.
[42] M. Lewinter and W. Widulski, "Hyper-Hamilton laceable and caterpillar-spannable product graphs," Computer and Mathematics with Applications, vol. 34, no. 11, pp. 99-104, 1997.
[43] T. K. Li, C. H. Tsai, J. M. Tan, and L. H. Hsu, "Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes," Information Processing Letters, vol. 87, no. 2, pp. 107-110, 2003.
[44] 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, no. 3, pp. 244-248, 2007.
[45] J. H. Park and H. C. Kim, "Fault-hamiltonicity of product graph of path and cycle," in Proceedings of 9th Annual International Conference (COCOON'03), LNCS 2697,
pp. 319-328, 2003.
[46] J.-H. Park, H.-S. Lim, and H.-C. Kim, "Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements," Theortical Computer Science, 377(1-3): 170-180, 2007.
[47] Y. Saad and M. H. Schultz, "Topological properties of hypercubes," IEEE Transactions on Computers , vol. 37, issue 7, pp. 867-872, 1988.
[48] A. Sen, A. Sengupta, and S. Bandyopadhyay, "On some topological properties of hypercube, incomplete hypercube and supercube," in Proceedings of the International
Parallel Processing Symposium, Newport Beach, pp. 636-642, 1993.
[49] A. Sengupta, "On ring embedding in hypercubes with faulty nodes and links," Information Processing Letters, vol. 68, issue 4, pp. 207-214, 1998.
[50] G. Simmons, "Almost all n-dimensional retangular lattices are Hamilton laceable," Congressus Numerantium, vol. 21, pp. 103-108, 1978.
[51] C. M. Sun, C. K. Lin, H. M. Huang and L. H. Hsu, "Mutually independent Hamiltonian paths in hypercubes," Jornal of Interconnection Networks, vol. 7, no. 2, pp. 235-255, 2006.
[52] C. H. Tsai, J.M. Tan, T. Liang, and L. H. Hsu, "Fault-tolerant Hamiltonian laceability of hypercubes," Information Processing Letters, vol. 83, no. 6, pp. 301-306,
2002.
[53] C. H. Tsai, "Linear array and ring embedding in conditional faulty hypercubes," Theoretical Computer Science, vol. 314, pp. 431-443, 2004.
[54] C. H. Tsai, and Y. C. Lai, "Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes," Information Sciences, vol. 177, issue 24, pp. 5590-5597, 2007.
[55] Y. C. Tseng, "Embedding a ring in a hypercube with both faulty links and faulty nodes," Information Processing Letters, vol 59, issue 4, pp. 217-222, 1996.
[56] D. Wang, "Embedding Hamiltonian cycles into folded hypercubes with faulty links," Journal of Parallel and Distributed Computing, vol. 61, no. 4, pp. 545-564, 2001.
[57] D. B. West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, NJ07458, 2001.
[58] Junming Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer academic publishers, 2001.
[59] J. M. Xu and M. J. Ma, "Cycles in folded hypercubes," Applied Mathematics Letters, vol. 19, issue 2, pp. 140-145, 2006.
[60] J. M. Xu, M. J. Ma, and Z. Z. Du, "Edge-fault-tolerant properties of hypercubes and folded hypercubes," Australasian Journal of Combinatorics, vol. 35, pp. 7-16, 2006.
[61] P. J. Yang, S. B. Tien, and C. S. Raghavendra, "Embedding of rings and meshes
onto faulty hypercubes using free dimensions," IEEE Transactions on Computers, vol. 43, issue 5, pp. 608-613, 1994.
[62] M. C. Yang, J. M. Tan, and L. H. Hsu, "Highly fault-tolerant cycle embeddings of hypercubes," Journal of Systems Architecture, vol. 53, issue 4, pp. 227-232, 2007.
[63] M. C. Yang, T. K. Li, J.M. Tan, and L. H. Hsu. "Fault-tolerant cycle-embedding of crossed cubes. " Information Processing Letters,, 88(4): 149-154, 2003.