Fully Dynamic Algorithms for 2-Edge Connectivity

DOI10.1137/0221062MaRDI QIDQ4027863zbMATH OpenOpenAlexFDO

Authors Giuseppe F. Italiano, Zvi Galil

Publication date 9 March 1993

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0221062

zbMATH Keywords

dynamic data structuresedge connectivityvertex connectivity

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• Fully dynamic 2-edge-connectivity in planar graphs
• Near-optimal fully-dynamic graph connectivity
• Quasi-fully dynamic algorithms for two-connectivity and cycle equivalence
• Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems
• Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity
• Faster deterministic fully-dynamic graph connectivity
• scientific article; zbMATH DE number 1775391
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Dynamic 2-Connectivity with Backtracking
• scientific article; zbMATH DE number 1256640

Cited in

(17)

• Dynamic connectivity for axis-parallel rectangles
• Quasi-fully dynamic algorithms for two-connectivity and cycle equivalence
• Decremental 2- and 3-connectivity on planar graphs
• Optimal offline dynamic 2, 3-edge/vertex connectivity
• Maintaining the 3-Edge-Connected Components of a Graph On-Line
• Dynamic 2-Connectivity with Backtracking
• scientific article; zbMATH DE number 1003251 (Why is no real title available?)
• Incremental 2-edge-connectivity in directed graphs
• Fully Dynamic 2-Hop Cover Labeling
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
• Fast sequential importance sampling to estimate the graph reliability polynomial
• Maintenance of 2- and 3-Edge-Connected Components of Graphs II
• Fully dynamic 2-edge-connectivity in planar graphs
• Maintenance of triconnected components of graphs
• Maintenance of 2- and 3-edge-connected components of graphs. I
• Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems
• Graph connectivity, partial words, and a theorem of Fine and Wilf

This page was built for publication: Fully Dynamic Algorithms for 2-Edge Connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027863)