﻿ 推广立方连通圈网络的Hamilton分解的算法

# 推广立方连通圈网络的Hamilton分解的算法The Algorithms for the Hamiltonian Decomposition of the General Cube-Connected Cycles Network

Abstract: The cube-connected cycles network is a hypercube of bounded-degree derivative. It has almost all of the excellent properties of hypercube. It also overcomes the shortcoming of hypercube vertices of degrees which will increase with the augment of the network size. But the cube-connected cycles network is simple or complex? This is an open question. Chordal ring network is a kind of classical interconnection network, which has the advantages of simple structure and so on. In this article, a model of the regular graph connected cycle network which is proposed by Haizhong Shi is used to design a kind of network which contains the cube-connected cycles network—the generalized cube-connected network GCCC(n) (n > 2). The authors prove that GCCC(n) (n > 2) can be decomposed into union of edge-disjoint a Hamiltonian cycle and a perfect matching, namely, GCCC(n) (n > 2) is a chordal ring network. They also make a algorithm for GCCC(n) (n > 2) can be decomposed into union of edge-disjoint a Hamiltonian cycle and a perfect matching.

[1] Akers, S.B., Harel, D. and Krishnamurthy, B. (1987) The Star Graph: An Attractive Alternative to the n-Cube. Proceeding of the 1987 International conference on Parallel Processing, The Pennsylvania University Press, Philadelphia, 393-400.

[2] Akers. S.B. and Krishnamurthy, B. (1989) A Group-Theoretic Model for Symmetric Interconnection Networks. IEEE Transactions on Computers, 38, 555-565. http://dx.doi.org/10.1109/12.21148

[3] Ohring, S.R., Sarkar, F. and Hohndel, D.H. (1995) Cayley Graph Connected Cycles: A New Class of Fixed-Degree Interconnection Networks. Proceeding of the 28th annual Hawaii International Conference on System Science, 3-6 January 1995, 479-488. http://dx.doi.org/10.1109/hicss.1995.375509

[4] 师海忠. 互连网络的代数环模型[D]: [博士学位论文]. 北京: 中国科学院应用数学研究所, 1998.

[5] 徐俊明. 组合网络理论[M]. 北京: 科学出版社, 2007.

[6] Efe, K. (1991) A Variation on the Hypercube with Lower Diameter. IEEE Transactions on Computer, 40, 1312-1316. http://dx.doi.org/10.1109/12.102840

[7] Ei-Amawy, A. and Latifi, S. (1991) Properties and Performance of Folded Hypercubes. IEEE Transactions on Parallel and Distributed Systems, 2, 31-42. http://dx.doi.org/10.1109/71.80187

[8] Cull, P. and Larson, S.M. (1995) The Mǒbius Cube. IEEE Transactions on Computer, 44, 647-659. http://dx.doi.org/10.1109/12.381950

[9] Efe, K. (1998) The Crossed Cube Architecture for Parallel Computation. IEEE Transactions on Parallel and Distributed Systems, 3, 513-523. http://dx.doi.org/10.1109/71.159036

[10] Hsu, L.-H. and Lin, C.-K. (2009) Graph Theory and Interconnection Networks. CRC Press, New York.

[11] 师海忠. 正则图连通圈: 多种互连网络的统一模型[C]//中国运筹学会. 中国运筹学会第十届学术交流会论文集. Hong Kong: Global-link Informatics Limited, 2010: 202-208.

[12] 师海忠, 牛攀峰, 马继勇, 侯菲菲. 互连网络的向量图模型[J]. 运筹学学报, 2011, 15(3): 115-123.

[13] 师海忠, 路建波. 关于互连网络的几个猜想[J]. 计算机工程与应用, 2008, 44(31): 112-115.

[14] 师海忠. 互连网络的新模型: 多部群论模型[J]. 计算机科学, 2013, 40(9): 21-24.

[15] 师海忠. 几类新的笛卡尔乘积互连网络[J]. 计算机科学, 2013, 40(6A): 265-270.

[16] Shi, H. and Shi, Y. (2015) A New Model for Interconnection Network: K-Hierarchical Ring and R-Layer Graph Network. http://vdisk.weibo.com/s/dlizJyferZ-Zl

[17] Shi, H. and Shi, Y. (2010) A Hierarchical Ring Group-Theoretic Model for Intercon-nection Networks. http://vdisk.weibo.com/s/dlizJyfeBX-2J

[18] Shi, H. and Shi, Y. (2015) Cell-Breading Graph Model for Interconnection Networks. http://vdisk.weibo.com/s/dlizJyfesb05y

[19] Preparata, F.P. and Vuillemin, J. (1981) The Cube-Connected Cycles: A Versatile Network for Parallel Computation. Communications of the Association for Computing Machinery, 24, 300-309. http://dx.doi.org/10.1145/358645.358660

[20] Annexstein, F., Baumslag, M. and Rosenberg, A.L. (1990) Group Action Graphs and Parallel Architectures, SIAM Journal on Computing, 19, 544-569. http://dx.doi.org/10.1137/0219037

[21] Bruck, J., Cypher, R. and Ho, C.-T. (1995) On the Construction of Fault-Tolerant Cube-Connected Cycles Networks. Journal Parallel and Distributed Compu-ting, 25, 98-106. http://dx.doi.org/10.1006/jpdc.1995.1032

[22] Friš, I., Havel, I. and Liebl, P. (1997) The Diameter of the Cube-Connected Cycles. Information Processing Letters, 61, 157-160. http://dx.doi.org/10.1016/S0020-0190(97)00013-6

[23] Stong, R. (1987) On Hamiltonian Cycles in Cayley Graphs of Wreath Products. Discrete Mathematics, 65, 75-80. http://dx.doi.org/10.1016/0012-365X(87)90212-3

[24] Miller, F.P. (2010) Cube-Connected Cycles. VDM Verlag Dr. Müller, Saarbrücken.

[25] Li, H., Hsu, T.-H., Ho, Y.-H. and Tsay, C.-W. (2014) Cycles in Cube-Connected Graph. Discrete Applied Ma-thematics, 167, 163-171. http://dx.doi.org/10.1016/j.dam.2013.11.021

[26] Biggs, N. (1993) Algebraic Graph Theory. 2nd Edition, Cambridge University Press, Cambridge.

[27] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan Press Ltd., London.

[28] 师海忠, 常立婷, 赵媛, 张欣, 王海峰. 2r-正则图连通圈网络的Hamilton分解[J]. 计算机科学, 2016, 43(11A) (已录用).

Top