Premium
A note on Arc tolerances in sparse shortest‐path and network flow problems
Author(s) -
Gusfield Dan
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130204
Subject(s) - arc (geometry) , shortest path problem , tracing , flow (mathematics) , path (computing) , computer science , graph , mathematics , algorithm , spacetime , tree (set theory) , space (punctuation) , combinatorics , geometry , physics , quantum mechanics , programming language , operating system
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 (n 2 ) time and O (n 2 ) 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.