NCJ Number
60690
Date Published
1977
Length
38 pages
Annotation
VARIOUS ALGORITHMS FOR THE DETECTION AND SUBSEQUENT TRACING OF NEGATIVE CYCLES IN A GRAPH ARE COMPARED.
Abstract
THE LITERATURE ON IDENTIFYING NEGATIVE CYCLES CAN BE DIVIDED INTO TWO MAJOR CLASSES: (1) SHORTEST PATH APPROACHES (ATTEMPTS TO FIND THE SHORTEST PATH IN A NETWORK), AND (2) DIRECT SEARCH APPROACHES (RELYING ON SOME SPECIAL PROPERTY POSSESSED BY NEGATIVE CYCLES). THE ALGORITHMS OF YEN, BENNINGTON, FORD-FULKERSON (SHORTEST PATH APPROACHES), AND FLORIAN (DIRECT SEARCH APPROACH) ARE EVALUATED. YEN, BENNINGTON, AND FLORIAN ARE CONSIDERED THE MOST EFFICIENT ALGORITHMS FROM THE FIELDS OF DYNAMIC PROGRAMING, LINEAR PROGRAMING, AND DIRECT SEARCH METHODS, RESPECTIVELY. FORD-FULKERSON, ALSO A DYNAMIC PROGRAMING BASED ALGORITHM, HAS PROVEN ITS RELIABILITY OVER TIME AND CAN ACT AS A 'CONTROL ALGORITHM' FOR COMPARING THE PERFORMANCE OF THE OTHER THREE. AN EXPERIMENTAL DESIGN IS USED TO EVALUATE THE EFFECTS OF ALGORITHM, NODES, DENSITY, AND ARC DISTRIBUTION IN DETECTING NEGATIVE CYCLES ON RANDOM NETWORKS. EXTENSIVE ANALYSIS WAS PERFORMED ON THE COMPUTATIONAL TIME TO DETECT A NEGATIVE CYCLE AND THE SUM OF THE ARC COSTS AROUND THE CYCLE. A THIRD RESPONSE VARIABLE, A QUALITY INDEX, DEFINED AS THE ABSOLUTE VALUE OF THE SUM OF THE ARC COSTS AROUND THE CYCLE DIVIDED BY THE COMPUTATIONAL TIME TO DETECT AND TRACE THE CYCLE, SERVED AS AN ADDITIONAL MEANS OF COMPARING THE EFFICIENCY OF THE ALGORITHMS. RESULTS SHOW THE FLORIAN DIRECT SEARCH METHOD TO BE SUPERIOR TO THE OTHER ALGORITHMS IN LOCATING NEGATIVE CYCLES ON RANDOM NETWORKS. TABULAR AND GRAPHIC DATA ARE PROVIDED, ALONG WITH A BIBLIOGRAPHY. (RCB)