New sharpness properties, algorithms and complexity bounds for partitioning shortest path procedures

Building on the framework of partitioning shortest path (PSP) algorithms, the authors introduce two new methods that exhibit different types of sharpness properties, based on a refinement of the sharpness concept of Shier and Witzgall, They show that the first of these two methods, which they classify as globally sharp, has a complexity bound that is superior to the complexity bound for the previous PSP algorithm. THRESH-S, that exhibits the same sharpness properties. The second new method, which the authors classify as globally scan-sharp, has a better bound and exhibits sharpness properties that are nearly as comprehensive. Finally, they discuss methods for identifying negative cycles that possess a time-sharpness property.