A faster parallel algorithm for k-connectivity
From MaRDI portal
Publication:287014
DOI10.1016/S0020-0190(97)00015-XzbMATH Open1336.68277OpenAlexW2073153454MaRDI QIDQ287014FDOQ287014
Kazuo Iwama, T. Ohsawaa, C. Iwamoto
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40) Parallel algorithms in computer science (68W10)
Cites Work
- Efficient Parallel Algorithms for Testingkand Finding Disjoints-tPaths in Graphs
- Constructing a perfect matching is in random NC
- Parallel Prefix Computation
- Finding the maximum, merging, and sorting in a parallel computation model
- Network Flow and Testing Graph Connectivity
- A Simpler Parallel Algorithm for Graph Connectivity
- Title not available (Why is that?)
- Routing Problems on the Mesh of Buses
- Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
Cited In (6)
- An efficient \({\mathcal {NC}}\) algorithm for a sparse \(k\)-edge-connectivity certificate
- OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks
- Title not available (Why is that?)
- A faster parallel connectivity algorithm on cographs
- Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
- Efficient Parallel Algorithms for Testingkand Finding Disjoints-tPaths in Graphs
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)
