论文部分内容阅读
讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n2logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决.
The minimum interception problem between two nodes in an undirected planar network with capacity constraints is discussed. The traditional method is to convert the smallest interception problem in a network with capacity nodes and edges into a problem with only capacity side, However, this method can not maintain the flatness of the network when it is used in a planar network, so the planarity of the network can not be utilized. The calculation time using the traditional method is O (n2logn) (where n is the number of nodes in the network) By using the method of network flatness, the algorithm of O (n) time can be obtained by transforming the minimal cut-off problem into the source and sink coplanar st-planar networks, and then the general planar network , A new method is proposed to transform the problem of capacity of both nodes and edges into a solution with only capacity problems. This transformation method does not destroy the planarity of the network, so that the method of calculating the capacity of a planar network can be used , So that the original problem is solved in O (nlogn) time.