On mixed connectivity certificates

DOI10.1016/S0304-3975(98)00023-1MaRDI QIDQ1274334zbMATH OpenFDO

Authors Shimon Even, Gene Itkis, Sergio Rajsbaum

Publication date 12 January 1999

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(98)00023-1

zbMATH Keywords

connectivity certificatesdistributed algorithmmixed connectivity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• On mixed connectivity certificates
• Sparse graph certificates for mixed connectivity
• Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs
• Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components

Cites work

• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Grad und lokaler Zusammenhang in endlichen Graphen
• scientific article; zbMATH DE number 3121292 (Why is no real title available?)
• scientific article; zbMATH DE number 3627227 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• scientific article; zbMATH DE number 3338382 (Why is no real title available?)
• On sparse subgraphs preserving connectivity properties
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• Sub-linear distributed algorithms for sparse certificates and biconnected components
• The multi-tree approach to reliability in distributed networks
• Über minimal n-fach zusammenhängende, unendliche Graphen und ein Extremalproblem. (On minimal n-fold connected infinite graphs and an extremal problem)

Cited in

(5)

• Sparse graph certificates for mixed connectivity
• Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs
• On mixed connectivity certificates
• Space complexity of vertex connectivity oracles
• Sparse connectivity certificates via MA orderings in graphs

This page was built for publication: On mixed connectivity certificates

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