A faster parallel algorithm for k-connectivity

DOI10.1016/S0020-0190(97)00015-XMaRDI QIDQ287014zbMATHOpenAlexFDO

Authors Kazuo Iwama, C. Iwamoto, T. Ohsawaa

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00015-x

zbMATH Keywords

computational complexityparallel algorithms\(k\)-connectivityPRAM

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40) Parallel algorithms in computer science (68W10)

Recommendations

• A Simpler Parallel Algorithm for Graph Connectivity
• A faster parallel connectivity algorithm on cographs
• Parallel algorithms for connectivity problems in graph theory
• An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph
• Parallel algorithms for finding connected components of a graph
• scientific article; zbMATH DE number 3930349
• scientific article; zbMATH DE number 1057772
• Efficient Parallel Algorithms for Testingkand Finding Disjoints-tPaths in Graphs
• An optimal parallel connectivity algorithm
• scientific article; zbMATH DE number 4068310

Cites work

• scientific article; zbMATH DE number 1555967 (Why is no real title available?)
• A Simpler Parallel Algorithm for Graph Connectivity
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• Constructing a perfect matching is in random NC
• Efficient Parallel Algorithms for Testingkand Finding Disjoints-tPaths in Graphs
• Finding the maximum, merging, and sorting in a parallel computation model
• Network Flow and Testing Graph Connectivity
• Parallel Prefix Computation
• Routing Problems on the Mesh of Buses

Cited in

(6)

• A faster parallel connectivity algorithm on cographs
• An efficient \({\mathcal {NC}}\) algorithm for a sparse \(k\)-edge-connectivity certificate
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks
• Efficient Parallel Algorithms for Testingkand Finding Disjoints-tPaths in Graphs
• scientific article; zbMATH DE number 1555967 (Why is no real title available?)

This page was built for publication: A faster parallel algorithm for \(k\)-connectivity

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