《幾類k元n維互連網路的交叉數算法研究及套用》是依託山西大學，由鄭文萍擔任項目負責人的面上項目。
基本介紹
- 中文名：幾類k元n維互連網路的交叉數算法研究及套用
- 項目類別：面上項目
- 項目負責人：鄭文萍
- 依託單位：山西大學
項目摘要,結題摘要,
項目摘要
互連網路拓撲結構決定著高性能計算系統和網路的通訊性能，其交叉數與網路布局的計算機輔助設計直接相關。確定一個圖的交叉數是NP困難問題，研究它對解決一般NP困難問題有重要借鑑意義。本課題將計算機構造與數學證明相結合，研究幾類典型的互連網路：k元n維立方體、Augmented k元n維立方體、k元n維蝶形網、混洗交換網和DeBruijn網的交叉數性質。(1)設計有效的計算策略，研製計算k元n維互連網路交叉數上界的算法；(2)利用計算結果，分析網路特徵，構造擴展性和實用性好的平面布局畫法；(3)給出有效的交叉數分組統計技術，結合網路拓撲屬性，發展新的交叉數下界證明方法。在k元n維互連網路的交叉數問題方面開展系統全面的研究，探索大規模互連網路的交叉數研究方法。本項目研究將豐富利用計算機算法解決圖論問題的理論成果，對交叉數在互連網路拓撲設計、電子線路板設計等領域的研究有重要理論意義和套用。
結題摘要
隨著信息技術的飛速發展，可供研究的領域數據越來越豐富，大規模網路的理論研究、算法設計、套用實施和平台架構為基於大數據的定量化分析提供了研究基礎，推動了系統生物學、社會學、心理學、管理學等多個學科發展。 互連網路拓撲結構決定著高性能計算系統和網路的通訊性能，其交叉數與網路布局的計算機輔助設計直接相關。確定一個圖的交叉數是NP困難問題，本項目對k元n維立方體網路的交叉數問題展開研究。計算n和k較小時，k元n維立方體的全局交叉數，設計了有效的分支限界策略，以有效的過濾同構子圖，平衡子圖的刪邊數和中間子圖數之間的計算時間代價，計算了k不大於4，n不大於9時的k元n維立方體的交叉數。並將此結果用於計算小規模De Bruijn圖的交叉數問題。互連網路頂點數隨著n和k的增大呈指數增長，交叉點數等拓撲屬性值也急劇增長。對n，k進一步增大時， k元n維立方體、De Bruijn圖等互連網路圖的交叉數及畫法布局複雜度急劇增大，計算全局交叉數更加困難。因此轉而考慮網路的局部拓撲屬性，計算網路中的重要節點，圍繞這些關鍵節點構造了局部網路的具有較好交叉點數的好的畫法。基於此，我們對k元n維立方體及其相關網路在n、k進一步增大的交叉數上界進行了計算，給出了一種具有較少交叉點數的局部子網路的畫法以及將局部子畫法組合成整個網路具有較少交叉點數的好的畫法。 此外，課題結合大規模複雜網路的網路聚集係數、特徵路徑長度、網路集簇性質、模組性等拓撲屬性，將網路節點重要性的評估方法和圖的同構判定方法套用於Web服務發現問題、圖聚類算法及複雜網路建模等問題中，設計開發了一個大規模網路數據處理平台。
