平面图及近似平面图上的最大流和最小割

最大流和最小割问题是计算机科学与运筹学的经典问题，在很多应用领域中起重要作用。平面图上的问题在最大流和最小割研究历史上一直得到特别关注，这是因为：（1） 平面图出现在VLSI等很多应用领域中；（2）平面图的特殊性质可用来设计高效算法。近年来，平面图相关问题的算法取得了很多突破性进展，使平面图问题的研究再次成为热点。本项目在现有工作基础上迎接新的挑战，目标是：（1）使平面图的最大流和最小割算法达到最优；（2）进一步降低平面图最小割树、近似平面图最大流等算法的时间复杂度；（3）给出多源多汇平面图最大流、有向平面图全局最小割等问题的可利用平面性算法。本项目将在充分发挥现有技术方法的基础上，研发新的数据结构和算法策略，最大程度地挖掘平面图的结构特性，以完成上述挑战性目标。本项目将实现平面图的最大流和最小割及相关问题算法复杂度的一系列突破，为相关应用领域提供更高效算法，具有深刻的理论意义和应用价值。