Date of Graduation
2003
Document Type
Thesis
Degree Type
MS
Committee Chair
K. Subramani
Abstract
In this thesis, we develop a greedy algorithm for the problem of checking whether a directed graph with positive and negative costs on its edges has a negative cost cycle. Our approach is the first known greedy strategy for this problem; all known approaches in the literature are based on Dynamic Programming. It is well known that the Negative Cost Cycle Detection problem is equivalent to the problem of checking whether a system of linear difference constraints is feasible. Our algorithm exploits this equivalence and uses polyhedral projection on the polyhedron of difference constraints corresponding to the input graph to detect the presence of negative cost cycles. We use the Fourier-Motzkin elimination procedure to effect polyhedral projection and contrast the performance of our algorithm with the “standard” Bellman-Ford (BF) algorithm along with more sophisticated implementations of the BF algorithm, such as BFFI (BF with a FIFO queue), BFPR (BF with a predecessor array), BFFP (BF with a FIFO queue and a predecessor array), BFCT (BF with subtree disassembly) and GORC (the Goldberg-Radzik algorithm). Our experiments show that Vertex Contraction (VC) is always superior to BF, BFFI, and BFPR implementations, while it approaches the performance of the other algorithms in certain cases.
Recommended Citation
Kovalchick, Lisa L., "An empirical study of algorithms for the negative cost cycle detection problem." (2003). Graduate Theses, Dissertations, and Problem Reports (ETD). 10721.
https://researchrepository.wvu.edu/etd/10721