Stressing is Better Than Relaxing for Negative Cost Cycle Detection in Networks
- 423 Downloads
This paper is concerned with the problem of checking whether a network with positive and negative costs on its arcs contains a negative cost cycle. We introduce a fundamentally new approach for negative cost cycle detection; our approach, which we term as the Stressing Algorithm, is based on exploiting the connections between the Negative Cost Cyle Detection (NCCD) problem and the problem of checking whether a system of difference constraints is feasible. The Stressing Algorithm is an incremental, comparison-based procedure which is asymptotically optimal, modulo the fastest comparison-based algorithm for this problem. In particular, on a network with n vertices and m edges, the Stressing Algorithm takes O(m Open image in new window n) time to detect the presence of a negative cost cycle or to report that none exist. A very important feature of the Stressing Algorithm is that it uses zero extra space; this is in marked contrast to all known algorithms that require Ω(n ) extra space.
KeywordsMaximal Element Constraint System Recursive Call Incoming Edge Input Network
Unable to display preview. Download preview PDF.
- 1.Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice-Hall, Englewood Cliffs (1993)Google Scholar
- 3.Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill Book Company, Boston (1992)Google Scholar
- 6.Schrijver, A.: Theory of Linear and Integer Programming. John Wiley and Sons, New York (1987)Google Scholar