{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T06:16:06Z","timestamp":1773814566486,"version":"3.50.1"},"reference-count":4,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8533,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the article \u201cArc Tolerances in Shortest\u2010Path and Network Flow Problems\u201d by D. R. Shier and C. Witzgall, several methods were described to compute, relative to a given tree <jats:italic>T<\/jats:italic>, the \u201carc tolerance\u201d of each arc in a graph <jats:italic>G<\/jats:italic> of <jats:italic>n<\/jats:italic> nodes and <jats:italic>A<\/jats:italic> arcs. One method, the \u201cdead\u2010end retraction\u201d method was shown to take <jats:italic>O<\/jats:italic>(n<jats:sup>2<\/jats:sup>) time and <jats:italic>O<\/jats:italic>(n<jats:sup>2<\/jats:sup>) space, and another method, the \u201ccycle\u2010tracing\u201d method was shown to take <jats:italic>O(nA)<\/jats:italic> time but only <jats:italic>O(A)<\/jats:italic> 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 <jats:italic>O(A)<\/jats:italic> space and <jats:italic>O(A)<\/jats:italic> log <jats:italic>n)<\/jats:italic> time. In the cycle\u2010tracing method this is a strict improvement even for the dense case.<\/jats:p>","DOI":"10.1002\/net.3230130204","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T14:58:44Z","timestamp":1178895524000},"page":"191-196","source":"Crossref","is-referenced-by-count":14,"title":["A note on Arc tolerances in sparse shortest\u2010path and network flow problems"],"prefix":"10.1002","volume":"13","author":[{"given":"Dan","family":"Gusfield","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100402"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90137-5"},{"key":"e_1_2_1_4_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A.","year":"1974"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130204","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T09:16:32Z","timestamp":1697793392000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,6]]},"references-count":4,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1983,6]]}},"alternative-id":["10.1002\/net.3230130204"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130204","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,6]]}}}