登入選單

返回Google圖書搜尋

An Efficient Construction of Cactus Representation for Minimum Cuts in Undirected Networks

Simon Fraser University. Centre for Systems Science

出版	Simon Fraser University, Centre for Systems Science, 1992
URL	http://books.google.com.hk/books?id=rRLZZwEACAAJ&hl=&source=gbs_api

註釋

This paper first considers the problem of finding a maximum flow between a source vertex and a sink vertex in a capacitated network with a set of vertices and edges. The authors present a time algorithm that computes a maximum flow between two vertices, which are determined upon its completion. As an application of this algorithm, the paper considers the problem of constructing a cactus representation for all minimum cuts in a network. The previously known algorithms that construct such a representation for a capacitated network are based on the fact that the set of all minimum cuts can be divided into disjoint subsets, each of which can be obtained by solving a maximum flow problem, where both the source and sink are specified. This paper proposes a generalized algorithm in which the source and sink in each maximum flow problem can be chosen arbitrarily.