A note on Arc tolerances in sparse shortest‐path and network flow problems
- 1 June 1983
- Vol. 13 (2) , 191-196
- https://doi.org/10.1002/net.3230130204
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.Keywords
This publication has 3 references indexed in Scilit:
- Sensitivity analysis of minimum spanning trees and shortest path treesInformation Processing Letters, 1982
- Arc tolerances in shortest path and network flow problemsNetworks, 1980
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975