《平面圖及近似平面圖上的最大流和最小割》是依託大連理工大學,由張憲超擔任項目負責人的面上項目。
基本介紹
- 中文名：平面圖及近似平面圖上的最大流和最小割
- 依託單位：大連理工大學
- 項目類別：面上項目
- 項目負責人：張憲超
- 批准號：61070016
- 申請代碼：F0201
- 負責人職稱：教授
- 研究期限：2011-01-01 至 2011-12-31
- 支持經費：11（萬元）
項目摘要
最大流和最小割問題是計算機科學與運籌學的經典問題，在很多套用領域中起重要作用。平面圖上的問題在最大流和最小割研究歷史上一直得到特別關注，這是因為：（1） 平面圖出現在VLSI等很多套用領域中；（2）平面圖的特殊性質可用來設計高效算法。近年來，平面圖相關問題的算法取得了很多突破性進展，使平面圖問題的研究再次成為熱點。本項目在現有工作基礎上迎接新的挑戰，目標是：（1）使平面圖的最大流和最小割算法達到最優；（2）進一步降低平面圖最小割樹、近似平面圖最大流等算法的時間複雜度；（3）給出多源多匯平面圖最大流、有向平面圖全局最小割等問題的可利用平面性算法。本項目將在充分發揮現有技術方法的基礎上，研發新的數據結構和算法策略，最大程度地挖掘平面圖的結構特性，以完成上述挑戰性目標。本項目將實現平面圖的最大流和最小割及相關問題算法複雜度的一系列突破，為相關套用領域提供更高效算法，具有深刻的理論意義和套用價值。
