Document Open Access Logo

Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs

Authors Ran Duan, Kaifeng Lyu, Yuanhang Xie

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.43.pdf
  • Filesize: 469 kB
  • 14 pages

Document Identifiers

Author Details

Ran Duan
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Kaifeng Lyu
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Yuanhang Xie
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China

Funding

  • Duan, Ran: R. Duan is supported by a China Youth 1000-Talent grant.

Cite AsGet BibTex

Ran Duan, Kaifeng Lyu, and Yuanhang Xie. Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.43

Abstract

In a directed graph G=(V,E) with a capacity on every edge, a bottleneck path (or widest path) between two vertices is a path maximizing the minimum capacity of edges in the path. For the single-source all-destination version of this problem in directed graphs, the previous best algorithm runs in O(m+n log n) (m=|E| and n=|V|) time, by Dijkstra search with Fibonacci heap [Fredman and Tarjan 1987]. We improve this time bound to O(m sqrt{log n}+sqrt{mn log n log log n}), which is O(n sqrt{log n log log n}) when m=O(n), thus it is the first algorithm which breaks the time bound of classic Fibonacci heap when m=o(n sqrt{log n}). It is a Las-Vegas randomized approach. By contrast, the s-t bottleneck path has algorithm with running time O(m beta(m,n)) [Chechik et al. 2016], where beta(m,n)=min{k >= 1: log^{(k)}n <= m/n}.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Graph Algorithm
  • Bottleneck Path
  • Combinatorial Optimization

Metrics

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

References

  1. Georg Baier, Ekkehard Köhler, and Martin Skutella. On the k-splittable flow problem. In European Symposium on Algorithms, pages 101-113. Springer, 2002. Google Scholar
  2. Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert Endre Tarjan. Time bounds for selection. J. Comput. Syst. Sci., 7(4):448-461, 1973. Google Scholar
  3. O Boruvka. O jistem problemu minimalnim, praca moravske prirodovedecke spolecnosti 3, 1926. Google Scholar
  4. B. Chazelle. A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM, 47(6):1028-1047, 2000. Google Scholar
  5. Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, and Uri Zwick. Bottleneck paths and trees and deterministic graphical games. In LIPIcs-Leibniz International Proceedings in Informatics, volume 47. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  6. D. Cheriton and R. E. Tarjan. Finding minimum spanning trees. SIAM J. Comput., 5:724-742, 1976. Google Scholar
  7. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251-280, 1990. Computational algebraic complexity editorial. URL: http://dx.doi.org/10.1016/S0747-7171(08)80013-2.
  8. Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959. Google Scholar
  9. Ran Duan and Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 384-391. Society for Industrial and Applied Mathematics, 2009. Google Scholar
  10. Jack Edmonds and Richard M Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2):248-264, 1972. Google Scholar
  11. Elena Fernandez, Robert Garfinkel, and Roman Arbiol. Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths. Oper. Res., 46(3):293-304, 1998. URL: http://dx.doi.org/10.1287/opre.46.3.293.
  12. L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8(0):399-404, 1956. URL: http://dx.doi.org/10.4153/cjm-1956-045-5.
  13. Greg N Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing, 14(4):781-798, 1985. Google Scholar
  14. Michael L Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3):596-615, 1987. Google Scholar
  15. Harold N Gabow and Robert E Tarjan. Algorithms for two bottleneck optimization problems. Journal of Algorithms, 9(3):411-417, 1988. Google Scholar
  16. T. C. Hu. The maximum capacity route problem. Operations Research, 9(6):898-900, 1961. URL: http://www.jstor.org/stable/167055.
  17. Vojtech Jarnık. O jistém problému minimálnım. Práca Moravské Prırodovedecké Spolecnosti, 6:57-63, 1930. Google Scholar
  18. David R Karger, Philip N Klein, and Robert E Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM (JACM), 42(2):321-328, 1995. Google Scholar
  19. Joseph B Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, 7(1):48-50, 1956. Google Scholar
  20. S. Pettie and V. Ramachandran. An optimal minimum spanning tree algorithm. J. ACM, 49(1):16-34, 2002. Google Scholar
  21. Asaf Shapira, Raphael Yuster, and Uri Zwick. All-pairs bottleneck paths in vertex weighted graphs. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 978-985. Society for Industrial and Applied Mathematics, 2007. Google Scholar
  22. Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2):146-160, 1972. Google Scholar
  23. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. All-pairs bottleneck paths for general graphs in truly sub-cubic time. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 585-589. ACM, 2007. Google Scholar
  24. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th symposium on Theory of Computing, STOC '12, pages 887-898, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2213977.2214056.
  25. A. C. Yao. An O(|E| log log |V|) algorithm for finding minimum spanning trees. Info. Proc. Lett., 4(1):21-23, 1975. 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 Imprint Privacy Contact