Abstract | ||
---|---|---|
This paper is concerned with the problem of recognizing, m a graph with rational vector-weights associates 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 periodic (dynamic) graphs and to the validity of systems of recursive formulas. It was previously conjectured that combinatorial algorithms exist for the casesof two- and three-dimen- sional vector-weights. It is shown that strongly polynomial algorithms exist for any fixed dimension d. Moreover, these algorithms also estabhsh membership in the class. 1Y. On the other hand, )t 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 Iogspace reductions, The algorithms presented here solve the cycle detection problem by reducing it to instances of the parametric mmimum cycle problem. In the latter, graphs with edge-weights that are linear functions of d parameters are considered. The goal, roughly. is to find an assignment of the parameters such that the value of the minimum weight cycle is maximized. The technique we used in order to obtain strongly polynomial algorithms for the parametric minimum cycle problem N a general tool applicable to parametric extensions of a variety of other problems. |
Year | DOI | Venue |
---|---|---|
1993 | 10.1145/153724.153727 | J. ACM |
Keywords | Field | DocType |
NC algorithm,strongly polynomial algorithms periodic graphs,application of multidimensional search,periodic graph,application of parametric method | Discrete mathematics,Graph,Combinatorics,Computer science,Strongly polynomial,Periodic graph (geometry) | Journal |
Volume | Issue | ISSN |
40 | 4 | 0004-5411 |
Citations | PageRank | References |
28 | 1.50 | 15 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Edith Cohen | 1 | 3260 | 268.21 |
Nimrod Megiddo | 2 | 4244 | 668.46 |