@inproceedings{11857,
  abstract     = {Two edges e/sub 1/ and e/sub 2/ of an undirected graph are cycle-equivalent iff all cycles that contain e/sub 1/ also contain e/sub 2/, i.e., iff e/sub 1/ and e/sub 2/ are a cut-edge pair. The cycle-equivalence classes of the control-flow graph are used in optimizing compilers to speed up existing control-flow and data-flow algorithms. While the cycle-equivalence classes can be computed in linear time, we present the first fully dynamic algorithm for maintaining the cycle-equivalence relation. In an n-node graph our data structure executes an edge insertion or deletion in O(/spl radic/n log n) time and answers the query whether two given edges are cycle-equivalent in O(log/sup 2/ n) time. We also present an algorithm for plane graphs with O(log n) update and query time and for planar graphs with O(log n) insertion time and O(log/sup 2/ n) query and deletion time. Additionally, we show a lower bound of /spl Omega/(log n/log log n) for the amortized time per operation for the dynamic cycle-equivalence problem in the cell probe model.< >},
  author       = {Henzinger, Monika H},
  booktitle    = {35th Annual Symposium on Foundations of Computer Science},
  isbn         = {0-8186-6580-7},
  location     = {Santa Fe, NM, United States},
  pages        = {744 -- 755},
  publisher    = {Institute of Electrical and Electronics Engineers},
  title        = {{Fully dynamic cycle-equivalence in graphs}},
  doi          = {10.1109/sfcs.1994.365718},
  year         = {1994},
}