[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On efficient algorithms for bottleneck path problems with many sources

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or \(\max \min \)) path problem is to find the maximum value of path-minimum edge capacities among all paths, connecting s and t. It can be generalized by finding the bottleneck values between s and all possible t. These problems arise as subproblems in the known maximum flow problem, having applications in many real-life tasks. For any graph with n vertices and m edges, they can be solved in O(m) and O(t(m, n)) times, respectively, where \(t(m,n)=\min (m+n\log (n),m\alpha (m,n))\) and \(\alpha (\cdot ,\cdot )\) is the inverse Ackermann function. In this paper, we generalize of the bottleneck path problems by considering their versions with k sources. For the first of them, where k pairs of sources and targets are (offline or online) given, we present an \(O((m+k)\log (n))\)-time randomized and an \(O(m+(n+k)\log (n))\)-time deterministic algorithms for the offline and online versions, respectively. For the second one, where the bottleneck values are found between k sources and all targets, we present an \(O(t(m,n)+kn)\)-time offline/online algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Algorithm 3
Algorithm 4
Algorithm 5
Algorithm 6
Algorithm 7

Similar content being viewed by others

Data availability

Our paper has no associated data.

References

  1. Aho, A.V., Hopcroft, J.E., Ullman, J.D.: On finding lowest common ancestors in trees. In: Aho A.V. et al. (eds.) Proceedings of the 5th Annual ACM Symposium on Theory of Computing, ACM, pp. 253–265 (1973)

  2. Aumüller, M., Dietzfelbinger, M., Woelfel, P.: Explicit and efficient hash families suffice for cuckoo hashing with a stash. Algorithmica 70, 428–456 (2014)

    Article  MathSciNet  Google Scholar 

  3. Baier, G., Köhler, E., Skutella, M.: On the \(k\)-splittable flow problem. In: Möhring, R., Raman, R. (eds.). Proceedings of European Symposium on Algorithms, pp. 101–113, Springer (2002)

  4. Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theor. Comput. Sci. 321(1), 5–12 (2004)

    Article  MathSciNet  Google Scholar 

  5. Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM J. Comput. 22(2), 221–242 (1993)

    Article  MathSciNet  Google Scholar 

  6. Boruvka, O.: About a certain minimal problem. Proc. Morav. Soc. Nat Sci. 3(3), 37–58 (1926)

    Google Scholar 

  7. Camerini, P.M.: The min–max spanning tree problem and some extensions. Inf. Process. Lett. 7(1), 10–14 (1978)

    Article  MathSciNet  Google Scholar 

  8. Chazelle, B.: A minimum spanning tree algorithm with inverse-ackermann type complexity. J. ACM 47(6), 1028–1047 (2000)

    Article  MathSciNet  Google Scholar 

  9. Chechik, S. et al.: Bottleneck paths and trees and deterministic graphical games. In: Olliger, N., Vollmer, H. (ed.) Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, Dagstuhl: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 27:1-27:13 (2016)

  10. Duan, R., Lyu, K., Xie, Y.: Single-source bottleneck path algorithm faster than sorting for sparse graphs. In: Chatzigiannakis, I. et al. (eds.) Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, Dagstuhl: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 43:1-43:14 (2018)

  11. Duan, R., Pettie, S.: Fast algorithms for \((\max , \min )\)-matrix multiplication and bottleneck shortest paths. In: Johnson, D., Fiege, U. (eds.) Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, pp. 384–391 (2009)

  12. Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 264–284 (1972)

    Article  Google Scholar 

  13. Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)

    Article  MathSciNet  Google Scholar 

  14. Galler, B.A., Fischer, M.J.: An improved equivalence algorithm. Commun. ACM 7(5), 301–303 (1964)

    Article  Google Scholar 

  15. Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338–355 (1984)

    Article  MathSciNet  Google Scholar 

  16. Hopcroft, J.E., Ullman, J.D.: Set merging algorithms. SIAM J. Comput. 2(4), 294–303 (1973)

    Article  MathSciNet  Google Scholar 

  17. Kaibel, V., Peinhardt, M. On the bottleneck shortest path problem. Tech. rep. 06-22., Takustr. 7, 14195 Berlin: ZIB (2006)

  18. Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48–50 (1956)

    Article  MathSciNet  Google Scholar 

  19. Ljunggren, L., et al.: Railway timetabling: a maximum bottleneck path algorithm for finding an additional train path. Public Transp. 13, 597–623 (2021)

    Article  Google Scholar 

  20. Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36(6), 1389–1401 (1957)

    Article  Google Scholar 

  21. Shinn, T.-W., Takaoka, T.: Variations on the bottleneck paths problem. Theor. Comput. Sci. 575, 10–16 (2015)

    Article  MathSciNet  Google Scholar 

  22. Tarjan, R.E., van Leeuwen, J.: Worst-case analysis of set union algorithms. J. ACM 31(2), 245–281 (1984)

    Article  MathSciNet  Google Scholar 

  23. Vassilevska, V., Williams, R., Yuster, R.: All-pairs bottleneck paths for general graphs in truly sub-cubic time. In: Johnson, D., Fiege, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, pp. 585–589 (2007)

Download references

Funding

The work of the author Malyshev D.S. was conducted within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE).

Author information

Authors and Affiliations

  1. Coleman Tech LLC, 40 Mira Avenue, Moscow, Russia, 129090

    Kirill V. Kaymakov

  2. Laboratory of Algorithms and Technologies for Networks Analysis, National Research University Higher School of Economics, 136 Rodionova Str., Nizhny Novgorod, Russia, 603093

    Dmitry S. Malyshev

Authors
  1. Kirill V. Kaymakov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dmitry S. Malyshev
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed to the study conception and design. Material preparation was performed by Kirill Kaymakov and Dmitriy Malyshev. The first draft of the manuscript was written by Kirill Kaymakov and Dmitriy Malyshev and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Dmitry S. Malyshev.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The work of the author Malyshev D.S. was conducted within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kaymakov, K.V., Malyshev, D.S. On efficient algorithms for bottleneck path problems with many sources. Optim Lett 18, 1273–1283 (2024). https://doi.org/10.1007/s11590-024-02113-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-024-02113-0

Keywords

Search

Navigation