On the Least Deviant Path in a Graph

A \emph{least deviant path} between two vertices in a weighted graph is defined as a path that minimizes the difference between the largest and smallest edge weights on the path.
Algorithms are presented to determine the least deviant path. The fastest algorithm runs in \(O(|E|^{1.793})\), in the worst case. A type of two-dimensional binary search is used to achieve this running time.