最大流和最小割问题是计算机科学与运筹学的经典问题,在很多应用领域中起重要作用。平面图上的问题在最大流和最小割研究历史上一直得到特别关注,这是因为:(1) 平面图出现在VLSI等很多应用领域中;(2)平面图的特殊性质可用来设计高效算法。近年来,平面图相关问题的算法取得了很多突破性进展,使平面图问题的研究再次成为热点。本项目在现有工作基础上迎接新的挑战,目标是:(1)使平面图的最大流和最小割算法达到最优;(2)进一步降低平面图最小割树、近似平面图最大流等算法的时间复杂度;(3)给出多源多汇平面图最大流、有向平面图全局最小割等问题的可利用平面性算法。本项目将在充分发挥现有技术方法的基础上,研发新的数据结构和算法策略,最大程度地挖掘平面图的结构特性,以完成上述挑战性目标。本项目将实现平面图的最大流和最小割及相关问题算法复杂度的一系列突破,为相关应用领域提供更高效算法,具有深刻的理论意义和应用价值。
{{i.achievement_title}}
数据更新时间:2023-05-31
基于铁路客流分配的旅客列车开行方案调整方法
一种基于多层设计空间缩减策略的近似高维优化方法
基于文献计量学和社会网络分析的国内高血压病中医学术团队研究
新型树启发式搜索算法的机器人路径规划
"多对多"模式下GEO卫星在轨加注任务规划
平面图的边面染色和完备染色
平面图的词表示性质的组合学研究
1-平面图的结构及其应用研究
平面图与正则图的几个基本控制参数