《圖的團橫貫問題的算法和複雜性》是依託上海大學，由單而芳擔任項目負責人的面上項目。
基本介紹
- 中文名：圖的團橫貫問題的算法和複雜性
- 項目類別：面上項目
- 項目負責人：單而芳
- 依託單位：上海大學
- 批准號：60773078
- 申請代碼：F0201
- 負責人職稱：教授
- 研究期限：2008-01-01 至 2010-12-31
- 支持經費：26（萬元）
中文摘要
在圖論中，圖的橫貫是一類重要概念，它既是超圖橫貫概念的一類特例，又涵蓋了圖論中的眾多重要概念，如覆蓋、團覆蓋、弱染色、控制集和全控制集等，在計算機、通信網路的設計和選址問題中具有廣泛的套用。本項目研究圖的團橫貫和團獨立集問題的算法複雜性和極值問題。由於該類問題已被證明是NP-困難的，因此下列工作有著重要的研究價值：該類問題近似算法的設計與分析；重要網路圖類上該類問題多項式時間算法的設計與分析；所對應圖參數的界的估計和極值問題研究。算法複雜性和近似算法的研究是理論計算機科學和組合最佳化的重要任務之一，本項目的研究正是基於上述目標和任務，力圖推進國內圖論、理論計算機和組合最佳化的結合研究。
