An Oracle Strongly Polynomial Algorithm for Bottleneck Expansion Problems

DOI10.1080/10556780290027819zbMath1060.90067OpenAlexW2067600269MaRDI QIDQ4806342

Zhenhong Liu, Zhang, Jianzhong

Publication date: 18 June 2003

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556780290027819

zbMATH Keywords

Capacity expansionPolynomial algorithmBottleneck capacities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items

Expanding maximum capacity path under weighted sum-type distances, An inverse model for the most uniform problem, A class of inverse dominant problems under weighted \(l_{\infty }\) norm and an improved complexity bound for Radzik's algorithm, A class of node based bottleneck improvement problems

Cites Work

• Efficiently solvable special cases of bottleneck travelling salesman problems
• Inverse maximum capacity problems
• Some reverse location problems
• Constrained matroidal bottleneck problems
• The Constrained Bottleneck Problem in Networks
• Algorithms for two bottleneck optimization problems
• Bottleneck extrema
• Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem
• A class of bottleneck expansion problems