[{"type":"conference","publication_status":"published","language":[{"iso":"eng"}],"title":"Fully dynamic cycle-equivalence in graphs","publisher":"Institute of Electrical and Electronics Engineers","month":"11","_id":"11857","doi":"10.1109/sfcs.1994.365718","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H"}],"publication":"35th Annual Symposium on Foundations of Computer Science","date_published":"1994-11-01T00:00:00Z","conference":{"start_date":"1994-11-20","name":"FOCS: Symposium on Foundations of Computer Science","end_date":"1994-11-22","location":"Santa Fe, NM, United States"},"oa_version":"None","extern":"1","abstract":[{"text":"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.< >","lang":"eng"}],"status":"public","date_updated":"2023-02-17T09:58:04Z","year":"1994","date_created":"2022-08-16T08:29:08Z","quality_controlled":"1","page":"744 - 755","citation":{"mla":"Henzinger, Monika H. “Fully Dynamic Cycle-Equivalence in Graphs.” <i>35th Annual Symposium on Foundations of Computer Science</i>, Institute of Electrical and Electronics Engineers, 1994, pp. 744–55, doi:<a href=\"https://doi.org/10.1109/sfcs.1994.365718\">10.1109/sfcs.1994.365718</a>.","ieee":"M. H. Henzinger, “Fully dynamic cycle-equivalence in graphs,” in <i>35th Annual Symposium on Foundations of Computer Science</i>, Santa Fe, NM, United States, 1994, pp. 744–755.","chicago":"Henzinger, Monika H. “Fully Dynamic Cycle-Equivalence in Graphs.” In <i>35th Annual Symposium on Foundations of Computer Science</i>, 744–55. Institute of Electrical and Electronics Engineers, 1994. <a href=\"https://doi.org/10.1109/sfcs.1994.365718\">https://doi.org/10.1109/sfcs.1994.365718</a>.","ista":"Henzinger MH. 1994. Fully dynamic cycle-equivalence in graphs. 35th Annual Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science, 744–755.","apa":"Henzinger, M. H. (1994). Fully dynamic cycle-equivalence in graphs. In <i>35th Annual Symposium on Foundations of Computer Science</i> (pp. 744–755). Santa Fe, NM, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/sfcs.1994.365718\">https://doi.org/10.1109/sfcs.1994.365718</a>","ama":"Henzinger MH. Fully dynamic cycle-equivalence in graphs. In: <i>35th Annual Symposium on Foundations of Computer Science</i>. Institute of Electrical and Electronics Engineers; 1994:744-755. doi:<a href=\"https://doi.org/10.1109/sfcs.1994.365718\">10.1109/sfcs.1994.365718</a>","short":"M.H. Henzinger, in:, 35th Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 1994, pp. 744–755."},"scopus_import":"1","publication_identifier":{"isbn":["0-8186-6580-7"]},"article_processing_charge":"No","day":"01"}]