On Stability of Widest Path in Network Routing
Ahmad Hosseini *
East Institute of Science and Technology, Tehran, Iran.
Bita Kabir Baiki
East Institute of Science and Technology, Tehran, Iran.
*Author to whom correspondence should be addressed.
Abstract
The problem of widest path (WP) is a well-established topic in network routing and digital compositing. This paper contemplates one facet of the robustness of optimal solutions to the widest path; i.e., stability analysis of the WP problem. The study here deals with infimum and supremum perturbations which determine multiplicative changes each individual arc can tolerate conserving the optimality of a given WP. It is additionally illustrated how to determine these marginal values for all arcs, and an algorithm for computing all such values is proposed.
Keywords: Operations research, network routing, path finding, widest path.