ISSN:
1436-4646
Keywords:
Max-balanced flows
;
Hoffman's Theorem
;
bottleneck paths
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract LetD=(V, A) be a directed graph. A real-valued vectorx defined on the arc setA is amax-balanced flow forD if for every cutW the maximum weight over arcs leavingW equals the maximum weight over arcs enteringW. For vectorsl⩽u defined onA, we describe an analogue of Hoffman's circulation conditions for the existence of a max-balanced flowx satisfyingl⩽x⩽u. We describe an algorithm for computing such a vector, but show that minimizing a linear function over the set of max-balanced flows satisfyingl⩽x⩽u is NP-hard. We show that the set of all max-balanced flows satisfyingl⩽x⩽u has a greatest element under the usual coordinate partial order, and we describe an algorithm for computing this element. This allows us to solve several related approximation problems. We also investigate the set of minimal elements under the coordinate partial order. We describe an algorithm for finding a minimal element and show that counting the number of minimal elements is #P-hard. Many of our algorithms exploit the relationship between max-balanced flows and bottleneck paths.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01581095
Permalink
