Cut tree algorithms

被引：0

作者：

Goldberg, AV ^{[1
]}

Tsioutsiouliklis, K ^{[1
]}

机构：

[1] InterTrust STAR Lab, Sunnyvale, CA 94086 USA

来源：

PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 1999年

关键词：

D O I：

暂无

中图分类号：

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

学科分类号：

0812 ;

摘要：

This is an experimental study of algorithms for the cut tree problem. We study the Gomory-Hu and Gusfield's algorithms as well as heuristics aimed to make the former algorithm faster. We develop an efficient implementation of the Gomory-Hu algorithm. We also develop problem families for testing cut tree algorithms. In our tests, the Gomory-Hu algorithm with a right combination of heuristics was significantly more robust than Gusfield's algorithm.

引用

页码：376 / 385

页数：10

共 19 条

[1]

ANDERSON RJ, 1993, NETWORK FLOWS MATCHI, P1

[2]

APPLEGATE DL, 1997, COMMUNICATION

[3]

Chekuri CS, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P324

[4] On implementing the push-relabel method for the maximum flow problem [J].

Cherkassky, BV ;

Goldberg, AV .

ALGORITHMICA, 1997, 19 (04) :390-410

[5]

Derigs U., 1989, ZOR, Methods and Models of Operations Research, V33, P383, DOI 10.1007/BF01415937

[6]

Ford L. R, 1962, FLOWS NETWORKS

[7] Beyond the flow decomposition barrier [J].

Goldberg, AV ;

Rao, S .

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, :2-11

[8] A NEW APPROACH TO THE MAXIMUM-FLOW PROBLEM [J].

GOLDBERG, AV ;

TARJAN, RE .

JOURNAL OF THE ACM, 1988, 35 (04) :921-940

[9]

GOLDBERG AV, 1987, THESIS MIT

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

GOMORY, RE ;

HU, TC .

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

← 1 2 →