ISSN:
1432-0541
Keywords:
Graph algorithms
;
Combinatorial optimization
;
Network flow
;
Parametric optimization
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Many combinatorial optimization problems are solved by a sequence of network flow computations on a network whose edge capacities are given as a function of a parameter λ. Recently Galloet al. [7] made a major advance in solving such parametric flow problems. They showed that for an important class of networks, calledmonotone parametric flow networks, a sequence ofO(n) flow computations could be solved in the same worst-case time bound as a single flow. However, these results require one of two special assumptions: either that the λ values are presented in increasing or decreasing order; or that the edge capacity functions are affine functions of λ. In this paper we show how to remove both of these assumptions while obtaining the same running times as in [7]. This observation generalizes and unifies the two major results of [7], and allows its ideas to be applied to many new combinatorial problems. Of greatest importance, it allows the efficient application of binary search and successive binary search to a sequence of network flow problems.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01758775
Permalink
