《路徑冪圖的交叉數、算法與套用研究》是依託大連理工大學,由楊元生擔任項目負責人的面上項目。
基本介紹
- 中文名：路徑冪圖的交叉數、算法與套用研究
- 依託單位：大連理工大學
- 項目類別：面上項目
- 項目負責人：楊元生
- 負責人職稱：教授
- 批准號：60573022
- 研究期限：2006-01-01 至 2008-12-31
- 申請代碼：F0201
- 支持經費：26（萬元）
項目摘要
圖的交叉數在CAD中有廣泛的套用，如草圖的識別與重畫、電路板設計等。它是NP困難問題，研究它對解決一般NP困難問題很有意義。.到目前為止，只有很有限的一些圖族的交叉數得到了精確值，其成果主要集中在對完全圖，完全二分圖及部分正則圖的研究。但實際套用中遇到的圖更多的是非正則圖。本課題著重研究一類非正則圖- - 路徑冪圖的交叉數；同時，研製出較好的計算圖的交叉數的算法與計算圖的交叉數的上界的算法, 為圖的交叉數的實際套用提供更堅實的理論基礎。.在圖的交叉數問題研究領域，申請者已取得了部分國際領先成果，本項目的研究，將有助於我們在該領域繼續保持國際領先水平。
