Fully dynamic cycle-equivalence in graphs
Two 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<sup>2</sup> 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 model
Henzinger94.pdf
openaccess
1.19 MB
Adobe PDF
73269b96a1428dcc49d7cf1bdc0fed16