Answers are grounded in this paper and cite their sources.
The tolerance of an element of a combinatorial optimization problem with respect to a given optimal solution is the maximum change, i.e., decrease or increase, of its cost, such that this solution remains optimal. The bottleneck path problem, for given an edge-capacitated graph, a source, and a target, is to find the max-min value of edge capacities on paths between the source and the target. For this problem and a network with n vertices and m edges, there is known the Ramaswamy-Orlin-Chakravarty's algorithm to compute all tolerances in O(m+nlog n) time. In this paper, for any in advance given sample of the problem with pairwise distinct edge capacities, we present a constant-time algorithm for computing both tolerances of an arbitrary edge with a preprocessing time O(m α(m,n)), where α(·,·) is the inverse Ackermann function. For given k source-target pairs, our solution yields an O((α(m,n)+k)m)-time algorithm to find tolerances of all edges with respect to optimal paths between the sources and targets, while the known algorithm takes O(k(m+nlog n)) time to find them.
No takes yet. Share an insight, caveat, or question.
Kaymakov et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: