Detecting cycles in dynamic graphs in polynomial time
- 1 January 1988
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 398-406
- https://doi.org/10.1145/62212.62251
Abstract
Consider a digraph which has labels on its edges which are k-dimensional vectors. In this paper we show it is possible in polynomial time to determine if such a digraph contains a zero cycle, i.e., a cycle whose edge labels sum to the zero vector component-wise. This solves the open problem of finding cycles in dynamic graphs which was posed by Iwano and Steiglitz. Our solution has a time complexity of &Ogr;(|V| log(|V|)Z) where Z is the complexity of a linear programming problem. For the important cases of two and three dimensions we present &Ogr;(Z) time algorithms. The linear programming problems we solve have at most 2|E| variables and &Ogr;(|E| + |V| + k) constraints.Keywords
This publication has 0 references indexed in Scilit: