AN EFFICIENT DISTRIBUTED ALGORITHM FOR 3-EDGE-CONNECTIVITY

DOI10.1142/S0129054106004042MaRDI QIDQ5483379zbMATH OpenFDO

Authors Yung H. Tsin

Publication date 14 August 2006

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

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

zbMATH Keywords

3-edge-connected componentanalysis of algorithmscut-pairdistributed algorithmsgraph connectivitynetwork reliability

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Distributed algorithms (68W15) Analysis of algorithms (68W40)

Recommendations

• Yet another optimal algorithm for 3-edge-connectivity
• Distributed edge connectivity in sublinear time
• Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs
• scientific article; zbMATH DE number 4014044
• Distributed algorithms for \textsc{Edge Dominating Sets}
• A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity
• A simple certifying algorithm for 3-edge-connectivity
• A simple randomized 3-edge connected component algorithm
• A linear time algorithm for computing 3-edge-connected components in a multigraph

Cites work

• A general program scheme for finding bridges
• A linear time algorithm for computing 3-edge-connected components in a multigraph
• An efficient distributed algorithm for centering a spanning tree of a biconnected graph
• An incremental distributed algorithm for computing biconnected components in dynamic graphs
• Depth-First Search and Linear Graph Algorithms
• Some remarks on distributed depth-first search.

Cited in

(6)

• A simple certifying algorithm for 3-edge-connectivity
• Self-stabilizing computation of 3-edge-connected components
• scientific article; zbMATH DE number 4215341 (Why is no real title available?)
• An efficient distributed algorithm for finding all hinge vertices in networks
• Group connectivity under 3‐edge‐connectivity
• A simple 3-edge-connected component algorithm

This page was built for publication: AN EFFICIENT DISTRIBUTED ALGORITHM FOR 3-EDGE-CONNECTIVITY

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