×

Negative-cycle detection algorithms. (English) Zbl 0954.90057

Summary: We study the problem of finding a negative length cycle in a network. An algorithm for the negative cycle problem combines a shortest path algorithm and a cycle detection strategy, We survey cycle detection strategies, study various combinations of shorest path algorithms and cycle detection strategies and find the best combinations. One of our discoveries is that a cycle detection strategy of Tarjan greatly improves computational performance of a classical shortest path algorithm, making it competitive with the fastest known algorithms on a wide range of problems. As a part of our study, we develop problem families for testing negative cycle algorithms.

MSC:

90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI