On mixed connectivity certificates

DOI10.1007/3-540-60313-1_130MaRDI QIDQ6102287zbMATH OpenOpenAlexFDO

Authors Shimon Even, Gene Itkis, Sergio Rajsbaum

Publication date 8 May 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60313-1_130

Mathematics Subject Classification ID

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

Recommendations

• On mixed connectivity certificates
• Sparse graph certificates for mixed connectivity
• Small cuts and connectivity certificates: a fault tolerant approach
• Non-uniformly sound certificates with applications to concurrent zero-knowledge
• Verifiable communication on networks
• A meta-theorem for distributed certification
• Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem
• A certificate infrastructure for machine-checked proofs of conditional information flow
• A proposal for broad spectrum proof certificates

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
• 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

(4)

• On mixed connectivity certificates
• Sparse graph certificates for mixed connectivity
• Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem
• 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 Q6102287)