Advertisement

Stressing is Better Than Relaxing for Negative Cost Cycle Detection in Networks

  • K. Subramani
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3738)

Abstract

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.

Keywords

Maximal Element Constraint System Recursive Call Incoming Edge Input Network 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice-Hall, Englewood Cliffs (1993)Google Scholar
  2. 2.
    Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming 73, 129–174 (1996)zbMATHMathSciNetGoogle Scholar
  3. 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
  4. 4.
    Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman Company, San Francisco (1979)zbMATHGoogle Scholar
  5. 5.
    Goldberg, A.V.: Scaling algorithms for the shortest paths problem. SIAM Journal on Computing 24(3), 494–504 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Schrijver, A.: Theory of Linear and Integer Programming. John Wiley and Sons, New York (1987)Google Scholar
  7. 7.
    Subramani, K., Kovalchick, L.: A greedy strategy for detecting negative cost cycles in networks. Future Generation Computer Systems 21(4), 607–623 (2005)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • K. Subramani
    • 1
  1. 1.LDCSEEWest Virginia UniversityMorgantown

Personalised recommendations