An O(n^2) self-stabilizing algorithm for computing bridge-connected components

DOI10.1007/S006070050013zbMATH Open0926.68053OpenAlexW2143340273MaRDI QIDQ1293460FDOQ1293460

Authors: P. Pal Chaudhuri 

Publication date: 5 October 1999

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s006070050013

Recommendations

• A self-stabilizing algorithm for bridge finding
• A stabilizing algorithm for finding biconnected components
• Self-stabilizing computation of 3-edge-connected components
• Efficient systolic algorithm for finding bridges in a connected graph
• A fully-pipelined systolic algorithm for finding bridges on an undirected connected graph
• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets

zbMATH Keywords

self-stabilizing algorithmnetwork model of computation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Cited In (11)

• A self-stabilizing graph algorithm: Finding the cutting center of a tree
• Efficient systolic algorithm for finding bridges in a connected graph
• An improved self-stabilizing algorithm for biconnectivity and bridge-connectivity
• Self-stabilizing disconnected components detection and rooted shortest-path tree maintenance in polynomial steps
• A simple systolic method to find all bridges of an undirected graph
• An efficient distributed bridge-finding algorithm
• A self-stabilizing algorithm for finding articulation points
• A stabilizing algorithm for finding biconnected components
• A self-stabilizing algorithm for bridge finding
• Self-stabilizing computation of 3-edge-connected components
• Self-stabilizing disconnected components detection and rooted shortest-path tree maintenance in polynomial steps

This page was built for publication: An \(O(n^2)\) self-stabilizing algorithm for computing bridge-connected components

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