FINDING K-CUTS WITHIN TWICE THE OPTIMAL

被引：116

作者：

SARAN, H

VAZIRANI, VV

机构：

[1] Indian Inst of Technology, New Delhi

来源：

SIAM JOURNAL ON COMPUTING | 1995年 / 24卷 / 01期

关键词：

GRAPH PARTITIONING; MINIMUM CUTS; APPROXIMATION ALGORITHMS;

D O I：

10.1137/S0097539792251730

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Two simple approximation algorithms for the minimum k-cut problem are presented. Each algorithm finds a k cut having weight within a factor of (2-2/k) of the optimal. One algorithm is particularly efficient-it requires a total of only n-1 maximum flow computations for finding a set of near-optimal k cuts, one for each value of k between 2 and n.

引用

页码：101 / 108

页数：8

共 16 条

[1]

ARORA S, 1992, 33RD P IEEE S F COMP, P14

[2]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[3] OPTIMAL ATTACK AND REINFORCEMENT OF A NETWORK [J].

CUNNINGHAM, WH .

JOURNAL OF THE ACM, 1985, 32 (03) :549-561

[4]

DALHAUS E, 1992, 24TH P ANN ACM S THE, P241

[5]

Garey M. R., 1979, COMPUTERS INTRACTABI

[6]

GOLDBERG AV, 1987, 19TH P ACM S THEOR C, P136

[7]

Goldschmidt O., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P444, DOI 10.1109/SFCS.1988.21960

[8] MULTI-TERMINAL NETWORK FLOWS [J].

GOMORY, RE ;

HU, TC .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1961, 9 (04) :551-570

[9] CONNECTIVITY AND EDGE-DISJOINT SPANNING-TREES [J].

GUSFIELD, D .

INFORMATION PROCESSING LETTERS, 1983, 16 (02) :87-89

[10]

HE X, 1991, J ALGORITHMS, V12, P23

← 1 2 →