Arc tolerances in shortest path and network flow problems

DOI10.1002/net.3230100402zbMath0452.90082OpenAlexW2022363559MaRDI QIDQ3899835

Christoph Witzgall, Douglas R. Shier

Publication date: 1981

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230100402

zbMATH Keywords

computational complexityshortest path problemnetwork flow problemsrobustness of optimal solutionsarc tolerances

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Deterministic network models in operations research (90B10)

Related Items

\(k\)-shortest routing of trains on shunting yards ⋮ Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems ⋮ Minimum spanning trees in networks with varying edge weights ⋮ 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 ⋮ Global tolerances in the problems of combinatorial optimization with an additive objective function ⋮ Stability analysis in discrete optimization involving generalized addition operations ⋮ Extremal values of global tolerances in combinatorial optimization with an additive objective function ⋮ Efficient computation of tolerances in the weighted independent set problem for some classes of graphs ⋮ Stability of an optimal schedule ⋮ A tolerance-based heuristic approach for the weighted independent set problem ⋮ Qualitative investigation of path problems ⋮ Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs ⋮ Some concepts of stability analysis in combinatorial optimization ⋮ Stability of Networks in Stretchable Graphs ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis ⋮ A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs

Cites Work

• Accelerated Algorithms for Labeling and Relabeling of Trees, with Applications to Distribution Problems