互連網路拓撲結構圖的反饋數、算法及套用研究

《互連網路拓撲結構圖的反饋數、算法及套用研究》是依託大連理工大學,由徐喜榮擔任項目負責人的面上項目。

基本介紹

• 中文名：互連網路拓撲結構圖的反饋數、算法及套用研究
• 依託單位：大連理工大學
• 項目類別：面上項目
• 項目負責人：徐喜榮

項目摘要

本項目是研究互連網路拓撲結構圖的反饋數問題，它是計算機科學與組合數學和圖論交叉的研究課題。圖的反饋數問題來源於實際問題，在諸多領域如預防計算機死鎖，互連網避免廣播風暴以及電子電路檢測等問題中有著廣泛的套用。已經被證明求圖的反饋數問題是NP困難問題，研究它對解決一般NP困難問題有借鑑意義。. 本項目旨在研製出較好的計算圖的反饋數的算法，並以此研究與互連網路拓撲結構相關圖的反饋數；確定與互連網路拓撲結構相關圖的反饋數的緊的上下界；同時研究一般圖的反饋數儘可能緊的上下界；從而能更好的解決與反饋數有關的實際問題。. 本項目的研究將豐富利用計算機算法解決圖論問題的理論成果，對互連網路拓撲結構相關圖的反饋數的研究結果對互連網路的設計、網路性能的定量分析和評估起著重要的理論指導作用，也為下一代超大規模超級計算機系統的互連網路的設計提供進一步的理論依據。

結題摘要

本項目是研究互連網路拓撲結構圖的反饋數問題，它是計算機科學與組合數學和圖論交叉的研究課題。圖的反饋數問題來源於實際問題，在諸多領域如預防計算機死鎖，互連網路避免廣播風暴以及電子電路檢測等問題中有著廣泛的套用。求圖的反饋數問題已被證明是NP困難問題，其每一個進展都十分艱辛。研究它對解決一般NP困難問題有借鑑意義。　 本項目旨在研製出較好的計算圖的反饋數的算法，並以此研究與互連網路拓撲結構相關圖的反饋數；確定與互連網路拓撲結構相關圖的反饋數的緊的上下界；同時研究一般圖的反饋數儘可能緊的上下界，從而能更好的解決與反饋數有關的實際問題. 本項目已經研製出計算互連網路拓撲結構圖的反饋數算法；對與互連網路拓撲結構設計方法(笛卡兒乘積方法、線圖方法、Cayley方法)密切相關的幾個重要的圖類的反饋數進行了研究，得到了如下結果： (1)研究出與笛卡兒乘積方法相關的圖類: 局部扭立方體網路LTQn、交叉立方體網路CQn、增廣立方體網路AQn反饋數的上下界； (2)研究出與Cayley方法相關的圖類：冒泡排序圖Bubble-sort graph 、交錯群圖Alternating group graph 、(n,k)-星圖、(n,k)-arrangement圖的反饋數的上下界； (3)研究出與線圖方法相關的圖類：Kautz 有向圖 、Kautz無向圖UK(d,n)、Generalized Kautz有向圖反饋數緊的上下界； (4)研究出與亞循環圖相關的圖類：廣義彼特森圖Pertersen graph P(n,k)、Flower Snark相關圖、Knodel圖W3,n、W4,n和部分循環圖Cn(1,k)的反饋數的精確值； (5)研究出一般r-正則圖G中給定圍長為g的條件下的反饋數的上界，以及k-正則圖二部圖G的反饋數的上界。 本項目的研究結果豐富了利用計算機算法解決圖論問題的理論成果，對互連網路的設計、網路性能的定量分析和評估起到重要的理論指導作用，也為下一代超大規模超級計算機系統的互連網路的設計提供進一步的理論依據。