SRC Technical Note 1997-004

Fully Dynamic 2-Edge Connectivity Algorithm in Polylogarithmic Time per Operation

Monika Rauch Henzinger and Valerie King

This paper presents the first dynamic algorithm that maintains 2-edge connectivity in polylogarithmic time per operation. The algorithm is a Las-Vegas type randomized algorithm.

For a sequence of Omega(m_0) operations, where m_0 is the number of edges in the initial graph, the expected time for p insertions or deletions of edges is O(p log^5n) and the worst-case time for a query is O(log n). If only deletions are allowed then the cost for p updates is O(p log^4n) expected time.

• PostScript compressed with UNIX compress -- 120 Kbytes
  
• PostScript compressed with GNU compress (gzip) -- 120 Kbytes
  
• PostScript compressed with ZIP -- 104 Kbytes
  
• PostScript -- 264 Kbytes
  
• Portable Document Format (PDF) -- 176 Kbytes