A linear time algorithm for the maximum capacity path problem

DOI10.1016/0377-2217(91)90073-5MaRDI QIDQ809905zbMATH OpenOpenAlexFDO

Authors 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

bicriteria path problemlinear time algorithmmaximum capacity path problemmaxmin pathsworst-case complexity

Mathematics Subject Classification ID

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

Recommendations

• The Maximum Capacity Shortest Path Problem: Generation of Efficient Solution Sets
• Parallel algorithm to find maximum capacity paths
• A parallel algorithm for the maximal path problem
• A capacity scaling algorithm for the constrained maximum flow problem
• A Fast and Simple Algorithm for the Maximum Flow Problem
• Linear-Time Approximation Algorithms for the Max Cut Problem
• On a capacity scaling algorithm for the constrained maximum flow problem
• The continuous maximum capacity path interdiction problem
• An efficient algorithm for the minimum capacity cut problem
• The capacitated max \(k\)-cut problem

Cites work

• A note on two problems in connexion with graphs
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Faster algorithms for the shortest path problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 3694968 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3634041 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations
• Scaling algorithms for network problems
• The Min-Max Spanning Tree Problem and some extensions

Cited in

(21)

• The bottleneck \(k\)-MST
• The partial sum criterion for Steiner trees in graphs and shortest paths
• On combined minmax-minsum optimization
• Paths with minimum range and ratio of arc lengths
• Minmax regret solutions for minimax optimization problems with uncertainty
• Solving some lexicographic multi-objective combinatorial problems
• A note on practical construction of maximum bandwidth paths.
• The continuous maximum capacity path interdiction problem
• Expanding maximum capacity path under weighted sum-type distances
• An efficient heuristic algorithm for the bottleneck traveling salesman problem
• Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion
• The Maximum Capacity Shortest Path Problem: Generation of Efficient Solution Sets
• Chemins extrémaux d'un graphe doublement valué
• Possibilistic bottleneck combinatorial optimization problems with ill-known weights
• scientific article; zbMATH DE number 7255037 (Why is no real title available?)
• Maximum Capacity Path Interdiction Problem with Fixed Costs
• The absolute quickest 1-center problem on a cycle and its reverse problem
• The quickest root-leaf interdiction problem on tree networks
• On a pair of job-machine assignment problems with two stages
• Mixed route strategies for the risk-averse shipment of hazardous materials
• Bottleneck flows in unit capacity networks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q809905)