Accession Number : ADA194026

Title :   A Fast Parametric Maximum Flow Algorithm. Revision,

Corporate Author : PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE

Personal Author(s) : Gallo, Giorgio ; Grigoriadis, Michael D ; Tarjan, Robert E

PDF Url : ADA194026

Report Date : Jul 1987

Pagination or Media Count : 42

Abstract : The classical maximum flow problem sometimes occurs in settings in which the capacities are not fixed but are functions of a single parameters, and the goal is to find the value of the parameter such that the corresponding maximum flow or minimum cut satisfies some side condition. Finding the desired parameter value requires solving a sequence of related maximum flow problems. We shoe that the recent maximum flow algorithm of Goldberg and Tarjan can be extended to solve an important class of such parametric maximum flow problems, at the cost of only a constant factor in its worst case time bound. Faster algorithms for a variety of combinational optimization problems follow from our result. Keywords: Algorithms; Data structures; Graphs; Maximum glow; Network flows; Networks.

Descriptors :   *ALGORITHMS, *NETWORK FLOWS, COSTS, DATA BASES, GRAPHS, PARAMETERS, PARAMETRIC ANALYSIS, OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE