《圖的p-中心、控制集及核的理論與算法》是依託上海大學，由康麗英擔任項目負責人的面上項目。
基本介紹
- 中文名：圖的p-中心、控制集及核的理論與算法
- 項目類別：面上項目
- 項目負責人：康麗英
- 依託單位：上海大學
- 批准號：10571117
- 研究期限：2006-01-01 至 2008-12-31
- 申請代碼：A0409
- 支持經費：23（萬元）
- 負責人職稱：教授
中文摘要
圖的p-中心、控制集和核是圖論中三個密切相關的重要最佳化問題，都可歸屬於選址問題，具有重要的理論意義和廣泛的套用前景。本項目的研究涉及到圖論、組合最最佳化、選址科學與網路理論，是跨學科的交叉項目。本項目側重從算法角度研究上述三個問題，研究方法有創新。p-中心問題是選址科學的核心問題之一，控制集在設計p-中心問題的近似算法時起著重要作用，它也是圖論近三十年來發展最快的領域之一，而核問題是圖的獨立控制集問題在有向圖上的推廣，在完美圖猜想和List染色猜想的研究中有著重要的作用。本項目研究內容主要有：p-中心問題的近似算法及其在特殊網路上的多項式算法；圖的電力控制數、配對控制數的估界及其在特殊圖類上的多項式算法；有向圖k-核的存在性、特定結構網路的吸收數以及核在染色理論中的套用；函式控制數和其它控制參數的估界與極值圖的刻畫。本項目的研究將推進圖論、組合最最佳化、選址科學及網路理論的交叉研究。
