
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