Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity

DOI10.1137/0222013zbMath0767.68048OpenAlexW2078960854MaRDI QIDQ4037691

Ramakrishna Thurimella, Ming-Yang Kao, Joseph Cheriyan

Publication date: 16 May 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0222013

zbMATH Keywords

vertex connectivityCRCW PRAM

Mathematics Subject Classification ID

Stochastic network models in operations research (90B15) Connectivity (05C40) Distributed algorithms (68W15)

Related Items (19)

A Family of Tree-Based Generators for Bubbles in Directed Graphs ⋮ Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity ⋮ Parallel algorithms for connectivity problems on interval graphs ⋮ Sparse connectivity certificates via MA orderings in graphs ⋮ Unnamed Item ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ A family of tree-based generators for bubbles in directed graphs ⋮ Algorithms for dense graphs and networks on the random access computer ⋮ Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries ⋮ An efficient algorithm to solve connectivity problem on trapezoid graphs ⋮ A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms ⋮ Approximating minimum cuts under insertions ⋮ On mixed connectivity certificates ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs ⋮ Independence free graphs and vertex connectivity augmentation ⋮ Sparse graph certificates for mixed connectivity ⋮ On mixed connectivity certificates ⋮ Approximating unweighted connectivity problems in parallel

This page was built for publication: Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity