New Sharpness Properties, Algorithms and Complexity Bounds for Partitioning Shortest Path Procedures
Operations Research · 1989 · Volume 37 · Issue 4
Abstract
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.
Keywords
networks/graphs: distance algorithms
Enable JavaScript for citation tools and additional paper interactions.