Algorithms for the Widest Path Problem
Venkat Sasank Donavalli · 2013
The widest path problem is a graph problem which is defined as finding the most optimal path between two vertices in a weighted graph which has the maximum possible weight for the most minimum weighted edge in the path. The widest path problem has applications in, for example, max flows, network routing, digital imaging, and voting theory. The widest path problem is related to the shortest path problem and algorithms known to solve this problem can be modified to solve the widest path problem. However, a different and more complicated approach is often needed to get optimal algorithms. Many of these algorithms exist only in theoretical papers, and so a major contribution of this project will be to explain these algorithms in an accessible way. In this project I propose to study, compare, explain, and implement the algorithms known for solving the widest path problem and to investigate the various applications for this problem. I also intend to come up with an optimized distributed algorithm to help find the widest path for a highly dense graph.