Bottleneck problems are optimization problems on directed or undirected graphs with edge weights. They are related to problems that deal with finding structures that minimize the sum of edge weights, such as the well studied Shortest Path and Minimum Spanning Tree problems. Bottleneck problems deal with finding structures that maximize the minimum edge weight.

Bottleneck problems have important applications in fields that deal with network routing such as logistics and computer networking, and others like digital compositing. The Bottleneck Path problem appears as a subproblem in the algorithm by Edmonds and Karp [1] for solving the Maximum Flow problem and in the k-splittable flow algorithm [2].

In the thesis we look at three Bottleneck problems, namely the Bottleneck Path problem, the Bottleneck Spanning Tree problem and the Single Source Bottleneck Path problem. We explore various algorithms and techniques that are used in solving these problems and examine their runtime characteristics. We focus especially on the algorithms by Chechik, Kaplan, Thorup, Zamir, and Zwick 2016 [3] and Duan, Lyu, and Xie 2018 [4], that have been discovered within the last couple of years and give the best running time for their problem currently known.

• [1] Jack Edmonds and Richard M. Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems”. In: J. ACM 19.2 (Apr. 1972), pp. 248–264.
• [2] Georg Baier, Ekkehard Köhler, and Martin Skutella. “On the k-Splittable Flow Problem”. In: Algorithms — ESA 2002. Ed. by Rolf Möhring and Rajeev Raman. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 101–113.
• [3] Shiri Chechik et al. “Bottleneck Paths and Trees and Deterministic Graphical Games”. In: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Ed. by Nicolas Ollinger and Heribert Vollmer. Vol. 47. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016, 27:1–27:13.
• [4] 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). Ed. by Ioannis Chatzigiannakis et al. Vol. 107. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, 43:1–43:14.