Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
From MaRDI portal
Publication:1356881
DOI10.1006/jcss.1997.1291zbMath0877.68088OpenAlexW2151440203MaRDI QIDQ1356881
Donald B. Johnson, Panagiotis T. Metaxas
Publication date: 16 June 1997
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1997.1291
Related Items (4)
A faster parallel connectivity algorithm on cographs ⋮ The interval-merging problem ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Concurrent disjoint set union
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding Euler tours in parallel
- Sorting in \(c \log n\) parallel steps
- Depth-first search is inherently sequential
- On efficient parallel strong orientation
- Parallel ear decomposition search (EDS) and st-numbering in graphs
- Towards optimal parallel bucket sorting
- Parallel algorithms for the connected components and minimal spanning tree problems
- An Efficient Parallel Biconnectivity Algorithm
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Deterministic coin tossing with applications to optimal parallel list ranking
- New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
- Parallel Merge Sort
- Parallel Symmetry-Breaking in Sparse Graphs
- Computing connected components on parallel computers
- Efficient parallel algorithms for some graph problems
- An O(logn) parallel connectivity algorithm
- An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph
- Fast Connected Components Algorithms for the EREW PRAM
- Sorting on a parallel pointer machine with applications to set expression evaluation
- Implementation of simultaneous memory address access in models that forbid it
- A Parallel Algorithm for Computing Minimum Spanning Trees
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
