Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs

DOI10.1007/s10107-004-0517-8zbMath1079.90137OpenAlexW2159018822WikidataQ59592484 ScholiaQ59592484MaRDI QIDQ1771306

Ramkumar Ramaswamy, James B. Orlin, Nilotpal Chakravarti

Publication date: 19 April 2005

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/5065

zbMATH Keywords

Sensitivity analysisShortest path problemBottleneck shortest pathMaximum capacity path problem

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31)

Related Items

Approximating the stability region for binary mixed-integer programs ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Extending single tolerances to set tolerances ⋮ Efficient computation of tolerances in the weighted independent set problem for trees ⋮ Sensitivity analysis for bottleneck assignment problems ⋮ Multicriteria investment problem with Savage's risk criteria: theoretical aspects of stability and case study ⋮ Quantitative analysis of flow distributions in a multiuser telecommunication network ⋮ Analysis of the load distribution and internodal flows under different routing strategies in a multiuser network ⋮ Efficient computation of tolerances in the weighted independent set problem for some classes of graphs ⋮ Ordered weighted average combinatorial optimization: formulations and their properties ⋮ Scalable min-max multi-objective cyber-security optimisation over probabilistic attack graphs ⋮ A tolerance-based heuristic approach for the weighted independent set problem ⋮ Bottleneck flows in unit capacity networks ⋮ The continuous maximum capacity path interdiction problem ⋮ Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• NC algorithms for the Single Most Vital Edge problem with respect to shortest paths
• A simple version of Karzanov's blocking flow algorithm
• The k most vital arcs in the shortest path problem
• Finding the most vital edge with respect to minimum spanning tree in weighted graphs
• Parallel algorithms for finding the most vital edge with respect to minimum spanning tree
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• Advances in sensitivity analysis and parametric programming
• Parallel algorithm for finding the most vital edge in weighted graphs
• Undirected single-source shortest paths with positive integer weights in linear time
• Arc tolerances in shortest path and network flow problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A randomized linear-time algorithm to find minimum spanning trees