On the Least Deviant Path in a Graph

Abstract

A $leastdeviantpath$ 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.