A fast algorithm for the generalized parametric minimum cut problem and applications |
| |
Authors: | Dan Gusfield Charles Martel |
| |
Affiliation: | 1. Computer Science Division, University of California, 95616, Davis, CA, USA
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|