FLOW VARIATION IN MULTIPLE MIN-CUT CALCULATIONS

被引：5

作者：

FRISCH, IT

机构：

[1] Department of Electrical Engineering, Computer Sciences Electronics Research Laboratory, University of California, Berkeley

来源：

JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS | 1969年 / 287卷 / 01期

关键词：

D O I：

10.1016/0016-0032(69)90032-5

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A problem of interest in flow networks is that of finding the smallest disconnecting set. Let s, s′, and t be three distinct arbitrary vertices in a directed graph and let τs,t be the value of the smallest s-t-cut. A method is given for significantly reducing the number of steps needed to calculate τs,t once τs′,t has been found by the Ford-Fulkerson labelling algorithm. This new method, called the Flow Variation Algorithm, has been successfully used in finding the smallest disconnecting sets in graphs with up to ninety vertices and eight hundred branches. © 1969.

引用

页码：61 / &