《全一問題的最優解及相關問題的算法與複雜性研究》是依託南開大學，由李學良擔任項目負責人的面上項目。
基本介紹
- 中文名：全一問題的最優解及相關問題的算法與複雜性研究
- 項目類別：面上項目
- 項目負責人：李學良
- 依託單位：南開大學
- 批准號：10371060
- 申請代碼：A0409
- 負責人職稱：教授
- 研究期限：2004-01-01 至 2006-12-31
- 支持經費：13（萬元）
中文摘要
研究圖的最小全一問題及相關問題的解的算法與複雜性和近似算法。對於樹的全一問題的解的個數給出計數公式；尋求樹的最小全一問題的最優解的多項式時間算法；對於二部圖，確定其最小全一問題的最優解的算法是否NP-完備的，如果是，找到好的近似算法。對於一般圖的全一問題的解，找到一個多項式時間的圖論算法。對於一般圖的最小全一這個NP-完備問題，尋找好的近似算法以得到好的近似解。對於全一問題的一些變形情況，探討它們的全一問題和最小全一問題的解的存在性、算法與複雜性、以及近似算法等。對於有向圖及其他自動機問題、最小權的自動機問題探討其最優解的算法與近似算法。本項目的研究不僅具有很強的套用背景，而且具有大量而又挑戰性的問題，對於它們的研究具有重要的理論意義。另外，在去年結束的北京國際數學家大會上，有一個大會報告和幾個邀請報告都是有關組合最佳化和NP-完備問題及其近似算法的，因此本項目屬於國際數學研究的主流方向。
