Accession Number : ADA323469

Title :   Processor-Efficient Implementation of a Maximum Flow Algorithm,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Goldberg, Andrew V.

PDF Url : ADA323469

Report Date : JAN 1990

Pagination or Media Count : 16

Abstract : This paper describes two processor-efficient implementation of the Maximum Distance Discharge algorithm for the maximum flow problem. The maximum flow problem is a classical combinatorial optimization problem, which has been widely studied in the context of sequential computation. Recently, parallel algorithms for the problem have been studied as well. Although the problem is known to be P-complete significant speedups can be obtained by using a parallel algorithm for the problem, both in theory and in practice.

Descriptors :   *ALGORITHMS, *OPTIMIZATION, *COMBINATORIAL ANALYSIS, COMPUTATIONS, PARALLEL PROCESSING, SEQUENCES, FLOW, RANGE(DISTANCE).

Subject Categories : Numerical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE