几类k元n维互连网络的交叉数算法研究及应用

项目名称： 几类k元n维互连网络的交叉数算法研究及应用

项目编号： No.61272004

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 郑文萍

作者单位： 山西大学

项目金额： 60万元

中文摘要： 互连网络拓扑结构决定着高性能计算系统和网络的通讯性能，其交叉数与网络布局的计算机辅助设计直接相关。确定一个图的交叉数是NP困难问题，研究它对解决一般NP困难问题有重要借鉴意义。本课题将计算机构造与数学证明相结合，研究几类典型的互连网络：k元n维立方体、Augmented k元n维立方体、k元n维蝶形网、混洗交换网和DeBruijn网的交叉数性质。(1)设计有效的计算策略，研制计算k元n维互连网络交叉数上界的算法；(2)利用计算结果，分析网络特征，构造扩展性和实用性好的平面布局画法；(3)给出有效的交叉数分组统计技术，结合网络拓扑属性，发展新的交叉数下界证明方法。在k元n维互连网络的交叉数问题方面开展系统全面的研究，探索大规模互连网络的交叉数研究方法。本项目研究将丰富利用计算机算法解决图论问题的理论成果，对交叉数在互连网络拓扑设计、电子线路板设计等领域的研究有重要理论意义和应用。

中文关键词： 图论算法；互连网络；拓扑结构；复杂网络；图聚类算法

英文摘要： Network topology is one of crucial factors for interconnection networks since it determines the performance of a network. The crossing number of a network is directly related with the layout of the network. Determining the crossing number of a graph is NP-hard. Therefore, the researches on crossing number might provide a effective method to study NP-hard problems. Combined the computer aided design and mathematical method, the project is to study the crossing numbers of several representative types of k ary n dimensional interconnection networks- - k ary n cube, augmented k ary n cube, k ary n dimensional butterfly network, k ary n dimensional shuffle/exchange network and k ary n dimensional De Bruijn network. The main works of the project are: (1) Designing effecitive computing strategy, and develop an algorithm to compute the upper bound of the crossing numbers of the networks mentioned above. (2) Analysing the properties of the networks, to construct drawings that could be well extended and be easily applied to the real network. (3) Proposing new methods to prove the lower bounds of the crossing numbers of the networks, where new crossing grouping techniques and new functions to counting the number of crossings might be studied. In a word, the project will study the crossing numbers of the k ary n dimensiona

英文关键词： graph algorithm；networks；topology；complex networks；graph clustering