Abstract
We introduce a new problem that combines the well known All Pairs Shortest Paths (APSP) problem and the All Pairs Bottleneck Paths (APBP) problem to compute the shortest paths for all pairs of vertices for all possible flow amounts. We call this new problem the All Pairs Shortest Paths for All Flows (APSP-AF) problem. We firstly solve the APSP-AF problem on directed graphs with unit edge costs and real edge capacities in \(\tilde{O}(\sqrt{t}n^{(\omega+9)/4}) = \tilde{O}(\sqrt{t}n^{2.843})\) time, where n is the number of vertices, t is the number of distinct edge capacities (flow amounts) and O(n ω) < O(n 2.373) is the time taken to multiply two n-by-n matrices over a ring. Secondly we extend the problem to graphs with positive integer edge costs and present an algorithm with \(\tilde{O}(\sqrt{t}c^{(\omega+5)/4}n^{(\omega+9)/4}) = \tilde{O}(\sqrt{t}c^{1.843}n^{2.843})\) worst case time complexity, where c is the upper bound on edge costs.
This research was supported by the EU/NZ Joint Project, Optimization and its Applications in Learning and Industry (OptALI).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Galil, Z., Margalit, O.: On the Exponent of the All Pairs Shortest Path Problem. In: Proc. 32nd FOCS, pp. 569–575 (1991)
Chan, T.: More algorithms for all-pairs shortest paths in weighted graphs. In: Proc. 39th STOC, pp. 590–598 (2007)
Dobosiewicz, W.: A more efficient algorithm for the min-plus multiplication. International Journal of Computer Mathematics 32, 49–60 (1990)
Duan, R., Pettie, S.: Fast Algorithms for (max,min)-matrix multiplication and bottleneck shortest paths. In: Proc. 19th SODA, pp. 384–391 (2009)
Floyd, R.: Algorithm 97: Shortest Path. Communications of the ACM 5, 345 (1962)
Fredman, M.: New bounds on the complexity of the shortest path problem. SIAM Journal on Computing 5, 83–89 (1976)
Le Gall, F.: Faster Algorithms for Rectangular Matrix Multiplication. In: Proc. 53rd FOCS, pp. 514–523 (2012)
Han, Y.: An O(n 3(loglogn/logn)5/4) time algorithm for all pairs shortest paths. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 411–417. Springer, Heidelberg (2006)
Han, Y., Takaoka, T.: An O(n 3loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. SWAT, pp. 131–141. Springer, Heidelberg (2012)
Schönhage, A., Strassen, V.: Schnelle Multiplikation Groβer Zahlen. Computing 7, 281–292 (1971)
Takaoka, T.: Sub-cubic Cost Algorithms for the All Pairs Shortest Path Problem. Algorithmica 20, 309–318 (1995)
Takaoka, T.: A faster algorithm for the all-pairs shortest path problem and its application. In: Chwa, K.-Y., Munro, J.I. (eds.) COCOON 2004. LNCS, vol. 3106, pp. 278–289. Springer, Heidelberg (2004)
Vassilevska, V., Williams, R., Yuster, R.: All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time. Journal of Theory of Computing 5, 173–189 (2009)
Williams, V.: Breaking the Coppersmith-Winograd barrier. In: Proc. 44th STOC (2012)
Zwick, U.: All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication. Journal of the ACM 49, 289–317 (2002)
Zwick, U.: A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths. Algorithmica 46, 278–289 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shinn, TW., Takaoka, T. (2014). Combining All Pairs Shortest Paths and All Pairs Bottleneck Paths Problems. In: Pardo, A., Viola, A. (eds) LATIN 2014: Theoretical Informatics. LATIN 2014. Lecture Notes in Computer Science, vol 8392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54423-1_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-54423-1_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54422-4
Online ISBN: 978-3-642-54423-1
eBook Packages: Computer ScienceComputer Science (R0)