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)

zbMATH Keywords

analysis of algorithmsdistributed algorithmsgraph connectivitynetwork reliability3-edge-connected componentcut-pair

Mathematics Subject Classification ID

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

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

(5)

• Group connectivity under 3‐edge‐connectivity
• An efficient distributed algorithm for finding all hinge vertices in networks
• A simple 3-edge-connected component algorithm
• A simple certifying algorithm for 3-edge-connectivity
• Self-stabilizing computation of 3-edge-connected components

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)