1989/01/01 by Edith Cohen, Nimrod Megiddo · 42 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Theory and Algorithms #Complexity and Algorithms in Graphs #Dimension (graph theory) #Mathematics #Dynamic programming #Time complexity #Discrete mathematics #Combinatorics #Graph #Polynomial #Algorithm
paper · pdf · doi:10.1145/73007.73057
openalex publication_date 1989/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
This paper is concerned with the problem of recognizing, in a graph with rational vector-weights associated with the edges, the existence of a cycle whose total weight is the zero vector. This problem is known to be equivalent to the problem of recognizing the existence of cycles in dynamic graphs and to the validity of some systems of recursive formulas. It was previously conjectured that combinatorial algorithms exist for the cases of two- and three-dimensional vector-weights. The present paper gives strongly polynomial algorithms for any fixed dimension. Moreover, these algorithms also establish membership in the class NC. On the other hand, it is shown that when the dimension of the weights is not fixed, the problem is equivalent to the general linear programming problem under strongly polynomial and logspace reductions.