TY - JOUR

T1 - Space-time tradeoffs in negative cycle detection - An empirical analysis of the Stressing Algorithm

AU - Subramani, K.

AU - Tauras, C.

AU - Madduri, K.

N1 - Funding Information:
This research has been supported in part by the Air Force Office of Scientific Research under grant FA9550-06-1-0050 and in part by the National Science Foundation through Award CCF-0827397.

PY - 2010/1/15

Y1 - 2010/1/15

N2 - This paper discusses space-time tradeoffs associated with algorithms for the problem of detecting negative cost cycles in networks (NCCD). NCCD is one of the more ubiquitous problems in computer science and operations research, with applications ranging from program verification and real-time scheduling to image segmentation and shortest path identification. Typical algorithmic analysis, whether theoretical or empirical, focuses almost exclusively on the running time of the algorithm. However, there exist applications in which space is just as important a parameter as time is. This is especially true when the problem instances are very large, as is the case in program verification. Consequently, an algorithm that minimizes running time while ignoring the space overhead may be impractical. In this paper, we analyze a number of the more common algorithms for NCCD from the perspectives of both time and space, with a view towards providing a space-time tradeoff for the practitioner. All the algorithms discussed in this paper (with the exception of Network Simplex) run in O (m · n) time on a network with m arcs and n vertices; however, their space requirements range from O (1) (Stressing Algorithm) to Ω (n) (all the Bellman-Ford and Network Simplex variants). Our empirical results demonstrate that in the cases where space is paramount, the Stressing Algorithm is a useful alternative to the Bellman-Ford variants.

AB - This paper discusses space-time tradeoffs associated with algorithms for the problem of detecting negative cost cycles in networks (NCCD). NCCD is one of the more ubiquitous problems in computer science and operations research, with applications ranging from program verification and real-time scheduling to image segmentation and shortest path identification. Typical algorithmic analysis, whether theoretical or empirical, focuses almost exclusively on the running time of the algorithm. However, there exist applications in which space is just as important a parameter as time is. This is especially true when the problem instances are very large, as is the case in program verification. Consequently, an algorithm that minimizes running time while ignoring the space overhead may be impractical. In this paper, we analyze a number of the more common algorithms for NCCD from the perspectives of both time and space, with a view towards providing a space-time tradeoff for the practitioner. All the algorithms discussed in this paper (with the exception of Network Simplex) run in O (m · n) time on a network with m arcs and n vertices; however, their space requirements range from O (1) (Stressing Algorithm) to Ω (n) (all the Bellman-Ford and Network Simplex variants). Our empirical results demonstrate that in the cases where space is paramount, the Stressing Algorithm is a useful alternative to the Bellman-Ford variants.

UR - http://www.scopus.com/inward/record.url?scp=72749101379&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=72749101379&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2009.10.053

DO - 10.1016/j.amc.2009.10.053

M3 - Article

AN - SCOPUS:72749101379

SN - 0096-3003

VL - 215

SP - 3563

EP - 3575

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

IS - 10

ER -