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

DOI10.1007/S10107-004-0517-8zbMATH Open1079.90137DBLPjournals/mp/RamaswamyOC05OpenAlexW2159018822WikidataQ59592484 ScholiaQ59592484MaRDI QIDQ1771306FDOQ1771306

Authors: 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

Recommendations

• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Sensitive and parametric analysis of the maximum flow in a network
• Sensitivity analysis on the all pairs \(q\)-route flows in a network
• Sensitivity analysis for bottleneck assignment problems
• The Maximum Capacity Shortest Path Problem: Generation of Efficient Solution Sets
• scientific article; zbMATH DE number 792651
• Publication:4489157
• scientific article; zbMATH DE number 3991234
• Publication:4726020

zbMATH Keywords

Shortest path problemSensitivity analysisBottleneck shortest pathMaximum capacity path problem

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31)

Cites Work

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

Cited In (19)

• Approximating the stability region for binary mixed-integer programs
• Title not available (Why is that?)
• Scalable min-max multi-objective cyber-security optimisation over probabilistic attack graphs
• Note on a vertex stability radius in the shortest path problem
• The continuous maximum capacity path interdiction problem
• Bottleneck flows in unit capacity networks
• Ordered weighted average combinatorial optimization: formulations and their properties
• A tolerance-based heuristic approach for the weighted independent set problem
• Quantitative analysis of flow distributions in a multiuser telecommunication network
• Sensitivity analysis on the all pairs \(q\)-route flows in a network
• Extending single tolerances to set tolerances
• Sensitivity analysis for bottleneck assignment problems
• The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
• Analysis of the load distribution and internodal flows under different routing strategies in a multiuser network
• Multicriteria investment problem with Savage's risk criteria: theoretical aspects of stability and case study
• Efficient computation of tolerances in the weighted independent set problem for trees
• Efficient computation of tolerances in the weighted independent set problem for some classes of graphs
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems

This page was built for publication: Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs

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