首页   按字顺浏览 期刊浏览 卷期浏览 Parametric maximal flows in generalized networks – complexity and algorithms
Parametric maximal flows in generalized networks – complexity and algorithms

 

作者: G. Ruhe,  

 

期刊: Optimization  (Taylor Available online 1988)
卷期: Volume 19, issue 2  

页码: 235-251

 

ISSN:0233-1934

 

年代: 1988

 

DOI:10.1080/02331938808843341

 

出版商: Akademic-Verlag

 

关键词: Network Flows;Generalized Networks;Complexity;parametric Optimization

 

数据来源: Taylor

 

摘要:

The problem of determining parametric maximal flows in networks with gains is considered. A worst-case analysis with respect to the number of breakpoints in the optimal objective value function is performed for both parametric flows leaving the source and parametric capacities of the arcs. The result is an exponential growth of the number of breakpoints depending on the number of vertices in the underlying graph. From there, the idea of a horizontal approximation algorithm developed from Hamachee and Foulds [5] is extended to generalized flows. In each iteration the horizontal approach makes an improvement which is a piecewise linear function of the whole parameter interval. This process can be applied up to optimality

 

点击下载:  PDF (689KB)



返 回