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

项目名称： 平面图及近似平面图上的最大流和最小割

项目编号： No.61070016

项目类型： 面上项目

立项/批准年度： 2011

项目学科： 轻工业、手工业

项目作者： 张宪超

作者单位： 大连理工大学

项目金额： 11万元

中文摘要： 本项目在执行的一年时间内得到平面图最大流和最小割问题以下三个成果：（1）给出平面图以面为基础的存储结构（简称面基结构），在此基础上，给出无向平面图最小割问题的O(n)时间算法，这是相关问题的第一个线性时间算法（最优算法）；（2）给出反例，说明现有节点和边都有容量的平面图上最大流问题算法存在错误，并给出正确算法；（3）给出有向平面图上最小割问题O(nloglogn)时间算法，比现有O(nlogn)时间算法快logn/loglogn倍。在此基金支持下，我们还解决了基于最大流算法的Web社区发现问题，提出了两个Web链接分析模型。目前已发表论文3篇，录用论文3篇，投稿3篇。在人才培养方面，本项目培养硕士毕业生5名，在读博士研究生1名。项目负责人于2011年入选教育部新世纪优秀人才支持计划。

中文关键词： 平面图;最大流;最小割

英文摘要： During the one year period of this project, we got three results on maximum flow and minimum cut problems of planar graph as following. (1) We gave a fase-based storage structure for plananr graph, and based on this, gave an O(n)-time algorithm for the minimum cut problem of undirected planar graphs. This is the first linear time and optimal algorithm. (2) We gave a counter-example to show that existing algorithms for the maximum flow problem in planar grapsh with edge and vertex capacities contain flaws, and gave the correct algorithm. （3）We gave the first O(nloglogn) time algorithm for the minimum cut problem in directed plananr graphs, which is logn/loglogn times faster than current O(nlogn) time algorithm. We also solved the flow-based web community identification problem and gave two web link analysis models. Till now 3 papers have been published, 3 papers have been accepted and 3 papers have been submmited. The project also supported 3 master students and 1 PhD candidate. The pricinple investigator was elected to Program for New Century Excellent Talents in University.

英文关键词： planar graph;maximum flow;minimum cut