Technical Contributions Finding Negative Cycles *
M. Klein, R.K. Tibrewala · INFOR Information Systems and Operational Research · 1973
A simple transformation on the distances associated with edges incident to a vertex is used as a basis for locating negative cycles in a directed graph. ComptJtational experiments indicate that it is faster than several potentially competitive methods when used as a subroutine in an assignment problem algorithm proposed by Klein. The transformation may also be used to convert a graph into one with non-negative edges provided the graph has no negative cycles.