New Sharpness Properties, Algorithms and Complexity Bounds for Partitioning Shortest Path Procedures

Building on the framework of partitioning shortest path (PSP) algorithms, we introduce two new methods that exhibit different types of sharpness properties, based on a refinement of the sharpness concept of Shier and Witzgall. We show that the first of these two methods, which we 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 we classify as globally scan-sharp, has a better bound and exhibits sharpness properties that are nearly as comprehensive. Finally, we discuss methods for identifying negative cycles that possess a time-sharpness property.