Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
复制标题
计算具有边缘和顶点容量的无向平面网络中的最大流
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Guoliang Chen
中科院分区：
文献类型：
--
作者：
Xianchao Zhang;W. Liang;Guoliang Chen
本文研究了边容量和顶点容量同时存在的无向平面网络（EVC-网络）的最大流问题。以前的研究将无向平面EVC-网络的最小割问题转化为另一个只具有边容量的平面网络（EC-网络）的最小边割问题，从而可以在O（nlogn）时间内计算最小割或最大流值.在此基础上，本文给出了计算无向一般平面EVC-网络最大流的O（nlogn）时间算法和计算无向（s，t）-平面EVC-网络最大流的O（n）时间算法.因此，无向平面EVC-网络的最大流问题在计算复杂度方面与无向平面EC-网络的问题一样简单。
We study the maximum flow problem in an undirected planar network with both edge and vertex capacities (EVC-network). A previous study reduces the minimum cut problem in an undirected planar EVC-network to the minimum edge-cut problem in another planar network with edge capacity only (EC-network), thus the minimum-cut or the maximum flow value can be computed in O(nlogn) time. Based on this reduction, in this paper we devise an O(nlogn) time algorithm for computing the maximum flow in an undirected general planar EVC-network and an O(n) time algorithm for computing the maximum flow in an undirected (s,t)-planar EVC-network. As a result, the maximum flow problem in undirected planar EVC-networks is as easy as the problem in undirected planar EC-networks in terms of computational complexity.