Henzinger, Monika R.2007-01-182007-01-182007-01-181994https://infoscience.epfl.ch/handle/20.500.14299/239595Two edges e_1 and e_2 of an undirected graph are cycle-equivalent iff all cycles that contain e_1 also contain e_2, i.e., iff e_1 and e_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(sqrt(n.log n)) time and answers the query whether two given edges are cycle-equivalent in O(pow2(log(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² n) query and deletion time. Additionally, we show a lower bound of Ω(log n/log log n) for the amortized time per operation for the dynamic cycle-equivalence problem in the cell probe modelcomputational geometrydata structuresequivalence classesgraph theoryoptimising compilerscontrol-flow graphcycle-equivalencecycle-equivalence problemdata structuregraphsoptimizing compilersplanar graphsplane graphsquery timeundirected graphtext::conference output::conference proceedings::conference paper