PROCESSOR-EFFICIENT IMPLEMENTATION OF A MAXIMUM FLOW ALGORITHM

被引：10

作者：

GOLDBERG, AV

机构：

[1] Department of Computer Science, Stanford University, Stanford

来源：

INFORMATION PROCESSING LETTERS | 1991年 / 38卷 / 04期

基金：

美国国家科学基金会;

关键词：

PARALLEL ALGORITHMS; MAXIMUM FLOWS; COMBINATORIAL OPTIMIZATION; ALGORITHMS; PARALLEL COMPUTATION; NETWORK FLOWS; MAXIMUM FLOW;

D O I：

10.1016/0020-0190(91)90097-2

中图分类号：

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

学科分类号：

0812 ;

摘要：

We describe two parallel implementations of the Maximum Distance Discharge algorithm for the maximum flow problems. Both implementations achieve near-optimal speedup for up to a linear number of processors. One of the implementations uses a new dynamic array data structure.

引用

页码：179 / 185

页数：7

共 23 条

[1]

ADELSONVELSKI GM, 1985, FLOW ALGORITHMS

[2]

AHUJA RK, 1987, MIT1905 87 SLOAN SCH

[3] PARALLEL EVALUATION OF GENERAL ARITHMETIC EXPRESSIONS [J].

BRENT, RP .

JOURNAL OF THE ACM, 1974, 21 (02) :201-206

[4] ANALYSIS OF PREFLOW PUSH ALGORITHMS FOR MAXIMUM NETWORK FLOW [J].

CHERIYAN, J ;

MAHESHWARI, SN .

SIAM JOURNAL ON COMPUTING, 1989, 18 (06) :1057-1086

[5] DETERMINISTIC COIN TOSSING WITH APPLICATIONS TO OPTIMAL PARALLEL LIST RANKING [J].

COLE, R ;

VISHKIN, U .

INFORMATION AND CONTROL, 1986, 70 (01) :32-53

[6]

Cole R., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P511, DOI 10.1109/SFCS.1986.41

[7]

Ford L., 1962, FLOWS NETWORKS, V71, P1059, DOI 10.2307/2311955

[8]

Goldberg A.V., 1987, THESIS MASSACHUSETTS

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

GOLDBERG, AV ;

TARJAN, RE .

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

[10]

GOLDBERG AV, 1987, TR374 MIT LAB COMP S

← 1 2 3 →