《圖上若干基本NP難問題的算法研究》是依託電子科技大學,由肖鳴宇擔任醒目負責人的青年科學基金項目。
基本介紹
- 中文名：圖上若干基本NP難問題的算法研究
- 依託單位：電子科技大學
- 項目類別：青年科學基金項目
- 項目負責人：肖鳴宇
項目摘要,結題摘要,
項目摘要
本項目主要從參數算法、精確算法和近似算法的角度來研究計算機中一些基本的圖問題，其中包括被稱之為六個基本NP難問題的獨立集和點覆蓋問題，以及經典的最大流最小割問題的擴展- - 圖多分割問題。這些問題非常基礎，且套用相當廣泛，在整個計算機學科中影響深遠，同時這些問題也被研究得非常透徹，任何改進都將在計算機學科內受到強烈關注。項目申請者在這些問題上具有較強的科研基礎，近兩年研究獲得七個當前最優的參數算法、精確算法和近似算法，並解決一個近二十年的公開難題。.參數計算是本項目主要研究方法之一，研究的是一個很難的問題在某個參數較小的時候是否存在有效算法（參數算法）。基於申請人提出的最遠最小割技術和新的分支理論，本項目將有望進一步改進並簡化圖多分割問題的參數算法，3度圖及稀疏圖上獨立集和點覆蓋問題的各項算法。在新理論下參數計算中另一個公開難題還有望被解決。目前以上科研進展順利，預計3年完成。
結題摘要
本項目主要用計算理論中的新發展起來的分支——參數算法等方法來研究若干基本NP難問題，主要包括：獨立集、點覆蓋、邊支配集、圖多分割等問題。項目按照計畫全部完成，研究成果超過計畫的一倍。項目期間共研獲10餘個當前最佳的算法等。其中兩個基本參數算法被參數計算新聞快報《Parameterized Complexity News》中的Table of Races欄目收錄，是該欄目目前收錄的僅有兩項來自中國的研究結果；在圖多分割問題上解決了一個10餘年的公開難題；在超圖上的多分割研究結果及後續研究在EGRES Open等科學網站上被介紹。項目期間以項目負責人為第一作者在Algorithmica、Theoretical Computer Science、MFCS、ISAAC等國際重要期刊和會議發表學術論文21篇，接收併網上發表論文2篇，其中5篇屬於中國計算機協會2013年公布的的B區論文，6篇屬於C區論文。另外在投C區以上論文4篇。項目主要取得的研究結果如下： 1. 給出了超圖上3塊割問題的第一個多項式算法，被EGRES Open網站介紹同時算法被日本京都大學實現，在VLSI上得到套用。 2. 給出了多塊割問題一個常用的貪心分而治之算法的的緊緻近似率從而解決此問題中的一個10餘年的公開問題，同時得到多塊割問題目前最好的近似算法。 3. 改進了3度圖點覆蓋問題和邊支配集問題兩個基本問題的最佳參數算法，其結果在《Parameterized Complexity News》中的Table of Races欄目中被列出。 4. 改進了低度圖上獨立集問題的最佳精確算法，基於該結果有望改進1986年Robson給出的一般圖上的最佳結果。 5. 在其它圖多分割、反饋集、TSP、支配集等問題上給出了8個最佳參數算法、精確算法、核心化算法等。 項目（包括地方人才計畫等配套）資助學術交流包括：海外高校訪問7人次，參加國際並報告會議13人次，邀請海外專家訪問11人次等，國內高校訪問8人次。共培養10餘本科生和8名碩士研究生。
