A note on Arc tolerances in sparse shortest‐path and network flow problems
Dan Gusfield · Networks · 1983
Abstract In the article “Arc Tolerances in Shortest‐Path and Network Flow Problems” by D. R. Shier and C. Witzgall, several methods were described to compute, relative to a given tree T, the “arc tolerance” of each arc in a graph G of n nodes and A arcs. One method, the “dead‐end retraction” method was shown to take O(n2) time and O(n2) space, and another method, the “cycle‐tracing” method was shown to take O(nA) time but only O(A) space. For the important case of large sparse graphs, these methods either require excessive time, or excessive space. In this note implementations of both of the above methods are described which require O(A) space and O(A) log n) time. In the cycle‐tracing method this is a strict improvement even for the dense case.