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

DOI10.1007/S006070050013MaRDI QIDQ1293460zbMATHOpenAlexFDO

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

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)

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

Cited in

(11)

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

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)