Document Open Access Logo

Single Source Shortest Paths for All Flows with Integer Costs

Author Tadao Takaoka

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2015.56.pdf
  • Filesize: 361 kB
  • 12 pages

Document Identifiers

Author Details

Tadao Takaoka

Cite As Get BibTex

Tadao Takaoka. Single Source Shortest Paths for All Flows with Integer Costs. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 56-67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/OASIcs.ATMOS.2015.56

Abstract

We consider a shortest path problem for a directed graph with edges labeled with a cost and a capacity. The problem is to push an unsplittable flow $f$ from a specified source to all other vertices with the minimum cost for all f values. Let G = (V, E) with |V| = n and |E| = m. If there are t different capacity values, we can solve the single source shortest path problem t times for all f in O(tm + tn log n) time, which is O(m^2) when t = m. We improve this time to O(min{t, cn}m + cn^2), which is less than O(cmn) if edge costs are non-negative integers bounded by c. Our algorithm performs better for denser graphs.

Subject Classification

Keywords
  • information sharing
  • shortest path problem for all flows
  • priority queue
  • limited edge cost
  • transportation network

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993. Google Scholar
  2. N. Alon, Z. Galil, and O. Margalit. On the exponent of the all pairs shortest path problems. JCSS 54, 255-262, 1997. Google Scholar
  3. Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, and Amit Kumar. Approximation algorithms for the unsplittable flow problem. Algorithmica 47(1): 53-78, 2007. Google Scholar
  4. B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming 73, 129-174, 1996. Google Scholar
  5. Thomas F. Coleman and Jorge J. More. Estimation of sparse jacobian matrices and graph coloring problems. SIAM Journal on Numerical Analysis 20 (1): 187-209, 1983. Google Scholar
  6. E. V. Denardo and B. L. Fox. Shortest-route methods: I. reaching, pruning, and buckets. Operations Research 27, 161-186, 1979. Google Scholar
  7. R. B. Dial. Algorithm 360: Shortest path forest with topological ordering. CACM 12, 632-633, 1969. Google Scholar
  8. E. W. Dijkstra. A note on two problems in connexion with graphs. Numer. Math. 1, 269-271, 1959. Google Scholar
  9. Y. N. Dinits, N. Garg Y, and N. Goemans. On the single-source unsplittable flow problem. Combinatorica, Springer, 19(1), 17-41, 1999. Google Scholar
  10. Ran Duan and Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), pp. 384–391, 2009. Google Scholar
  11. Matthias Ehrgott. Multicriteria Optimization. Springer-Verlag, 2005. Google Scholar
  12. M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Jour. ACM 34, 596-615, 1987. Google Scholar
  13. Harold N. Gabow and Robert E. Tarjan. Algorithms for two bottleneck optimization problems. Journal of Algorithms 9 (3): 411–417, 1988. Google Scholar
  14. Tong-Wook Shinn and Tadao Takaoka. Combining all pairs shortest paths and all pairs bottleneck paths problems. LATIN 2014: 226-237, 2014. Google Scholar
  15. Tong-Wook Shinn and Tadao Takaoka. Combining the shortest paths and the bottleneck paths problems. ACSC 2014: 13-18, 2014. Google Scholar
  16. Tong-Wook Shinn and Tadao Takaoka. Some extensions of the bottleneck paths problem. WALCOM 2014: 176-187, 2014. Google Scholar
  17. Tadao Takaoka. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica 20(3): 309-318, 1998. Google Scholar
  18. Tadao Takaoka. Sharing information for the all pairs shortest path problem. Theor. Comput. Sci. 520: 43-50, 2014. Google Scholar
  19. M. Thorup. Integer priority queues with decrease key in constant time and the single source shortest paths problem. STOC03, 149-158, 2003. Google Scholar
  20. U. Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. Jour. ACM, 49, 3, 289-317, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact