Self-stabilizing computation of 3-edge-connected components

DOI10.1142/S0129054111008623MaRDI QIDQ3173942zbMATH OpenOpenAlexFDO

Authors Abusayeed Saifullah, Yung H. Tsin

Publication date 10 October 2011

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054111008623

zbMATH Keywords

fault-toleranceself-stabilizationdistributed systemdepth-first search tree3-edge-connected componentcut-pair

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• An \(O(n^2)\) self-stabilizing algorithm for computing bridge-connected components
• AN EFFICIENT DISTRIBUTED ALGORITHM FOR 3-EDGE-CONNECTIVITY
• A stabilizing algorithm for finding biconnected components
• Self-stabilizing depth-first search
• A self-stabilizing distributed algorithm to construct an arbitrary spanning tree of a connected graph

Cites work

• A belated proof of self-stabilization
• A self-stabilizing algorithm for coloring planar graphs
• A self-stabilizing algorithm for detecting fundamental cycles in a graph
• A self-stabilizing algorithm for finding articulation points
• A self-stabilizing distributed algorithm to find the median of a tree graph
• A stabilizing algorithm for finding biconnected components
• AN EFFICIENT DISTRIBUTED ALGORITHM FOR 3-EDGE-CONNECTIVITY
• An \(O(n^2)\) self-stabilizing algorithm for computing bridge-connected components
• An improved self-stabilizing algorithm for biconnectivity and bridge-connectivity
• Depth-First Search and Linear Graph Algorithms
• Self-stabilization
• Self-stabilizing depth-first search
• Self-stabilizing systems in spite of distributed control

Cited in

(4)

• Self-stabilizing disconnected components detection and rooted shortest-path tree maintenance in polynomial steps
• An \(O(n^2)\) self-stabilizing algorithm for computing bridge-connected components
• A stabilizing algorithm for finding biconnected components
• Self-stabilizing disconnected components detection and rooted shortest-path tree maintenance in polynomial steps

This page was built for publication: Self-stabilizing computation of 3-edge-connected components

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