On mixed connectivity certificates

DOI10.1016/S0304-3975(98)00023-1zbMath0913.68147MaRDI QIDQ1274334

Sergio Rajsbaum, Shimon Even, Gene Itkis

Publication date: 12 January 1999

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

zbMATH Keywords

distributed algorithm; connectivity certificates; mixed connectivity

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W15: Distributed algorithms

Related Items

Sparse connectivity certificates via MA orderings in graphs, Sparse graph certificates for mixed connectivity, Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs

Cites Work

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