Negative cycle detection problem

Chi Him Wong; Yiu Cheong Tam

doi:10.1007/11561071_58

Negative cycle detection problem

Chi Him Wong, Yiu Cheong Tam

Chinese University of Hong Kong

Research output: Contribution to journal › Conference article › peer-review

3 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	652-663
Number of pages	12
Journal	Lecture Notes in Computer Science
Volume	3669
DOIs	https://doi.org/10.1007/11561071_58
Publication status	Published - 2005
Externally published	Yes
Event	13th Annual European Symposium on Algorithms, ESA 2005 - Palma de Mallorca, Spain Duration: 3 Oct 2005 → 6 Oct 2005

Access to Document

10.1007/11561071_58

Cite this

@article{6baee08a801f4465a30dbb11e1932681,

title = "Negative cycle detection problem",

abstract = "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.",

author = "Wong, {Chi Him} and Tam, {Yiu Cheong}",

year = "2005",

doi = "10.1007/11561071_58",

language = "English",

volume = "3669",

pages = "652--663",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

note = "13th Annual European Symposium on Algorithms, ESA 2005 ; Conference date: 03-10-2005 Through 06-10-2005",

}

TY - JOUR

T1 - Negative cycle detection problem

AU - Wong, Chi Him

AU - Tam, Yiu Cheong

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

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

U2 - 10.1007/11561071_58

DO - 10.1007/11561071_58

M3 - Conference article

AN - SCOPUS:27144516214

SN - 0302-9743

VL - 3669

SP - 652

EP - 663

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 13th Annual European Symposium on Algorithms, ESA 2005

Y2 - 3 October 2005 through 6 October 2005

ER -

Negative cycle detection problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this