A Faster Algorithm for Least Deviant Path

Abstract

The least deviant path was defined by Klostermeyer $[1]$ as the path between two vertices $u$ and $v$ that minimizes the difference between the largest and smallest weights on the path. This paper presents an $O(E\log E)$ time algorithm for this problem in undirected graphs, improving upon the previously given $O(E^{1.793})$ time algorithm.
The same algorithm can also be used to solve the problem in $O(VE)$ time in directed graphs.