AN EFFICIENT ALGORITHM FOR THE MINIMUM CAPACITY CUT PROBLEM

被引：67

作者：

PADBERG, M ^{[1
]}

RINALDI, G ^{[1
]}

机构：

[1] CNR,IST ANALISI SISTEMI & INFORMAT,I-00185 ROME,ITALY

来源：

MATHEMATICAL PROGRAMMING | 1990年 / 47卷 / 01期

关键词：

computation; Minimum weighted cuts; networks; polynomial-time algorithms;

D O I：

10.1007/BF01580850

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given a finite undirected graph with nonnegative edge capacities the minimum capacity cut problem consists of partitioning the graph into two nonempty sets such that the sum of the capacities of edges connecting the two parts is minimum among all possible partitionings. The standard algorithm to calculate a minimum capacity cut, due to Gomory and Hu (1961), runs in O(n4) time and is difficult to implement. We present an alternative algorithm with the same worst-case bound which is easier to implement and which was found empirically to be far superior to the standard algorithm. We report computational results for graphs with up to 2000 nodes. © 1990 The Mathematical Programming Society, Inc.

引用

页码：19 / 36

页数：18

共 14 条

[1]

[Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265

[2] SOLVING LARGE-SCALE SYMMETRIC TRAVELING SALESMAN PROBLEMS TO OPTIMALITY [J].