《圖最佳化劃分問題的算法和複雜性研究》是依託南京師範大學，由張曉岩擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖最佳化劃分問題的算法和複雜性研究
- 項目類別：青年科學基金項目
- 項目負責人：張曉岩
- 依託單位：南京師範大學
- 批准號：10801077
- 申請代碼：A0409
- 負責人職稱：教授
- 研究期限：2009-01-01 至 2011-12-31
- 支持經費：17（萬元）
項目摘要
圖最佳化劃分問題是圖論與組合最佳化領域裡的一個基礎性問題，該問題要求將原圖劃分成頂點不交的p個部分，其中p>1，並對邊集合進行調整（刪除或添加）且滿足相關的最佳化目標。由於其在生物信息、並行計算、大規模積體電路設計、數據挖掘、圖像識別、以及大規模資料庫的有效存儲上都具有非常重要的套用，因此對該問題的研究在計算機科學領域裡也占有極其重要的位置。大部分具有套用價值和理論背景的圖最佳化劃分問題都是NP完全問題。我們根據圖最佳化劃分問題的特性將其分成兩大類型，著重選擇了當前在生物信息領域具有套用背景和在理論上與染色問題相關的圖最佳化劃分問題,尋求全局最佳化性能、魯棒性強、通用性強且適於並行處理的啟發式算法和進行高近似程度的近似算法、隨機算法的設計分析以及計算複雜性的研究。
