SRC Technical Note 1997-004a

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.

The expected time for p = Omega(m + n) insertions or deletions of edges is O(p log^5n), where m is the number of edges in the initial graph with n nodes. 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^4 n) expected time.

Back to the SRC Technical Notes main page.

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

Publication history

• Note #1997-004. June 12, 1997. 14 pages.