A note on Arc tolerances in sparse shortest-path and network flow problems

DOI10.1002/net.3230130204zbMath0514.90020OpenAlexW2157128732MaRDI QIDQ3661270

Dan Gusfield

Publication date: 1983

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230130204

zbMATH Keywords

large sparse graphscomputation of arc tolerancescycle tracingdead end retractiondirected tree of shortest paths

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Paths and cycles (05C38)

Related Items (8)

Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems ⋮ Minimum spanning trees in networks with varying edge weights ⋮ Extending single tolerances to set tolerances ⋮ Global tolerances in the problems of combinatorial optimization with an additive objective function ⋮ Stability analysis in discrete optimization involving generalized addition operations ⋮ Extremal values of global tolerances in combinatorial optimization with an additive objective function ⋮ Some concepts of stability analysis in combinatorial optimization ⋮ A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs

Cites Work

• Efficiency of a Good But Not Linear Set Union Algorithm

This page was built for publication: A note on Arc tolerances in sparse shortest-path and network flow problems