Technical Contributions Finding Negative Cycles*

1 February 1973

journal article
research article
Published by Taylor & Francis in INFOR: Information Systems and Operational Research

Vol. 11 (1) , 59-65
https://doi.org/10.1080/03155986.1973.11731536

Abstract

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.

Keywords

This publication has 4 references indexed in Scilit:

A Direct Search Method to Locate Negative Cycles in a Graph
Management Science, 1971
A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
Management Science, 1967
Algorithm 97: Shortest path
Communications of the ACM, 1962
A note on two problems in connexion with graphs
Numerische Mathematik, 1959