Journal of Applied Mathematics and Decision Sciences
Volume 2005 (2005), Issue 2, Pages 83-94
doi:10.1155/JAMDS.2005.83
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.
Abstract
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 x, a valid perturbation of cij(x) is a convex function that can be substituted for cij(x) in the total cost function without violating the optimality of x. Tolerance set for an arc(i,j) is the collection of all valid perturbations of cij(x). We characterize the tolerance set for each arc(i,j) in terms of nonsingleton shortest distances between nodes i and j. We also give an efficient algorithm to compute the nonsingleton shortest distances between all pairs of nodes in O(n3) time where n denotes the number of nodes in the given graph.