Negative cycle detection problem

Chi Him Wong, Yiu Cheong Tam

Research output: Contribution to journalConference articlepeer-review

3 Citations (Scopus)


In this paper, we will describe some heuristics that can be used to improve the runtime of a wide range of commonly used algorithms for the negative cycle detection problem significantly, such as Bellman-Ford-Tarjan (BFCT) algorithm, Goldberg-Radzik (GORC) algorithm and Bellman-Ford-Moore algorithm with Predecessor Array (BFCF). The heuristics are very easy to be implemented and only require modifications of several lines of code of the original algorithms. We observed that the modified algorithms outperformed the original ones, particularly in random graphs and no cycle graphs. We discovered that 69% of test cases have improved. Also, the improvements are sometimes dramatic, which have an improvement of a factor of 23, excluding the infinity case, while the worst case has only decreased by 85% only, which is comparably small when compared to the improvement.

Original languageEnglish
Pages (from-to)652-663
Number of pages12
JournalLecture Notes in Computer Science
Publication statusPublished - 2005
Externally publishedYes
Event13th Annual European Symposium on Algorithms, ESA 2005 - Palma de Mallorca, Spain
Duration: 3 Oct 20056 Oct 2005


Dive into the research topics of 'Negative cycle detection problem'. Together they form a unique fingerprint.

Cite this