Maintenance of 2- and 3-edge-connected components of graphs. I

DOI10.1016/0012-365X(93)90376-5zbMATH Open0795.05131OpenAlexW2050475090MaRDI QIDQ685694FDOQ685694

Authors: Johannes A. La Poutré, J. Van Leeuwen, Mark H. Overmars 

Publication date: 24 October 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(93)90376-5

Recommendations

• Maintenance of 2- and 3-Edge-Connected Components of Graphs II
• Maintaining the 3-Edge-Connected Components of a Graph On-Line
• Fully Dynamic Algorithms for 2-Edge Connectivity
• Decremental 2- and 3-connectivity on planar graphs
• Dynamic 2- and 3-connectivity on planar graphs

zbMATH Keywords

connectivitypathdynamic graph algorithm2- and 3-edge-connected components

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Efficiency of a Good But Not Linear Set Union Algorithm
• Parallel concepts in graph theory
• Title not available (Why is that?)
• Worst-case Analysis of Set Union Algorithms
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Title not available (Why is that?)
• Amortized efficiency of a path retrieval data structure
• Title not available (Why is that?)
• Maintenance of 2- and 3-Edge-Connected Components of Graphs II
• Maintaining bridge-connected and biconnected components on-line
• Finding paths and deleting edges in directed acyclic graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maintenance of triconnected components of graphs

Cited In (16)

• Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems
• The General Structure of Edge-Connectivity of a Vertex Subset in a Graph and its Incremental Maintenance. Odd Case
• Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity
• Maintaining bridge-connected and biconnected components on-line
• The connectivity carcass of a vertex subset in a graph and its incremental maintenance
• Incremental 2-edge-connectivity in directed graphs
• Maintenance of 2- and 3-Edge-Connected Components of Graphs II
• Maintaining the 3-Edge-Connected Components of a Graph On-Line
• Dynamic 2- and 3-connectivity on planar graphs
• A simple randomized 3-edge connected component algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)
• Augmenting the edge connectivity of planar straight line graphs to three
• Decremental 2- and 3-connectivity on planar graphs
• Connectivity oracles for graphs subject to vertex failures
• Maintenance of triconnected components of graphs

This page was built for publication: Maintenance of 2- and 3-edge-connected components of graphs. I

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