A linear time algorithm for the maximum capacity path problem

DOI10.1016/0377-2217(91)90073-5zbMath0732.90085OpenAlexW2090820749MaRDI QIDQ809905

Abraham P. Punnen

Publication date: 1991

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(91)90073-5

zbMATH Keywords

linear time algorithmworst-case complexitybicriteria path problemmaximum capacity path problemmaxmin paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (16)

On combined minmax-minsum optimization ⋮ Expanding maximum capacity path under weighted sum-type distances ⋮ Mixed route strategies for the risk-averse shipment of hazardous materials ⋮ Unnamed Item ⋮ Paths with minimum range and ratio of arc lengths ⋮ Possibilistic bottleneck combinatorial optimization problems with ill-known weights ⋮ Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion ⋮ Bottleneck flows in unit capacity networks ⋮ An efficient heuristic algorithm for the bottleneck traveling salesman problem ⋮ Maximum Capacity Path Interdiction Problem with Fixed Costs ⋮ On a pair of job-machine assignment problems with two stages ⋮ The partial sum criterion for Steiner trees in graphs and shortest paths ⋮ The bottleneck \(k\)-MST ⋮ The continuous maximum capacity path interdiction problem ⋮ Minmax regret solutions for minimax optimization problems with uncertainty ⋮ Solving some lexicographic multi-objective combinatorial problems

Cites Work

• A note on two problems in connexion with graphs
• Scaling algorithms for network problems
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• The Min-Max Spanning Tree Problem and some extensions
• Faster algorithms for the shortest path problem
• Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations
• Fibonacci heaps and their uses in improved network optimization algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A linear time algorithm for the maximum capacity path problem