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