Journal of Applied Mathematics and Decision Sciences
Volume 2005 (2005), Issue 2, Pages 83-94
A combinatorial arc tolerance analysis for network flow problems
1HCL Technologies Ltd. CODC, Chennai 600 026, India
2Department of Mathematics and Statistics, Indian Institute of Technology Kanpur, Kanpur 208 016, India
Received 10 July 2002; Revised 15 May 2003
Copyright © 2005 P. T. Sokkalingam and Prabha Sharma. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
For the separable convex cost flow problem, we consider the problem of determining tolerance set for each arc cost function. For a given optimal flow , a valid perturbation of is a convex function that can be substituted for in the total cost function without violating the optimality of . Tolerance set for an is the collection of all valid perturbations of . We characterize the tolerance set for each in terms of nonsingleton shortest distances between nodes and . We also give an efficient algorithm to compute the nonsingleton shortest distances between all pairs of nodes in time where denotes the number of nodes in the given graph.