几类互连网络拓扑结构图的交叉数算法及其应用研究

项目名称： 几类互连网络拓扑结构图的交叉数算法及其应用研究

项目编号： No.60973014

项目类型： 面上项目

立项/批准年度： 2010

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

项目作者： 杨元生

作者单位： 大连理工大学

项目金额： 30万元

中文摘要： 图G的交叉数cr(G)是图的一个拓扑不变量，它是衡量图的非平面性的一个重要量度。研究互连网络拓扑结构图的交叉数有助于确定网络交叉数和为制定该网络的VLSI线路所需要的平面布局二者之间的关系，以降低芯片造价。确定一个图的交叉数是NP困难问题，研究它对解决一般NP困难问题有重要的借鉴意义。 本项目将研究几类重要互联网络拓扑结构图(包括n-维星图Sn、薄饼图 Pn、冒泡排序图Bn、排列图An,k、交错群图AGn、(n,k)-星图Sn,k)的交叉数，以此研究一般互联网络拓扑结构图的交叉数的性质；同时，研制出较好的计算互联网络拓扑结构图的交叉数算法与计算互联网络拓扑结构图的交叉数的上界的算法。 本项目的研究将丰富利用计算机算法解决图论问题的理论成果，对图的交叉数在互联网络的拓扑设计、电子线路板的设计等领域的研究有重要的理论意义和应用价值。

中文关键词： 交叉数；算法设计与分析；互连网络；n-维星图；

英文摘要：

英文关键词： Crossing number；design analysis of algorithm；network；n-dimensional Star graph；