An O(logn) parallel connectivity algorithm
From MaRDI portal
Publication:3957960
DOI10.1016/0196-6774(82)90008-6zbMATH Open0494.68070OpenAlexW2004350101WikidataQ56813859 ScholiaQ56813859MaRDI QIDQ3957960FDOQ3957960
Authors: Uzi Vishkin, Yossi Shiloach 
Publication date: 1982
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(82)90008-6
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Theory of operating systems (68N25)
Cited In (80)
- Processor-time tradeoffs in PRAM simulations
- A parallel algorithm for eliminating cycles in undirected graphs
- Incomplete directed perfect phylogeny in linear time
- Chordal graph recognition is in NC
- Parallel computational geometry
- Fast connected-component labeling
- A linear systolic algorithm for the connected component problem
- Finding small simple cycle separators for 2-connected planar graphs
- Adapting parallel algorithms to the W-stream model, with applications to graph problems
- An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
- Communication-efficient parallel algorithms for distributed random-access machines
- A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
- Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
- \(O(\log \log n)\)-time integer geometry on the CRCW PRAM
- Vectorized search for single clusters
- Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
- A parallel algorithm for the maximum 2-chain edge packing problem
- Data reduction and fast routing: A strategy for efficient algorithms for message-passing parallel computers
- Optimal parallel algorithms on planar graphs
- Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
- Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
- Efficient parallel algorithms to test square-freeness and factorize strings
- An optimal parallel connectivity algorithm
- Optimal parallel algorithms for multiple updates of minimum spanning trees
- A complexity theory of efficient parallel algorithms
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Resource bounds for parallel computation of threshold and symmetric functions
- A parallel-design distributed-implementation (PDDI) general-purpose computer
- Static and dynamic parallel computation of connected components
- Finding Euler tours in parallel
- Efficient algorithms for acyclic colorings of graphs
- GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU
- Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
- Monte Carlo circuits for the abelian permutation group intersection problem
- Parallel ear decomposition search (EDS) and st-numbering in graphs
- Separation and lower bounds for ROM and nondeterministic models of parallel computation
- Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays
- A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
- A parallel algorithm for computing Steiner trees in strongly chordal graphs
- On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
- Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
- An efficient algorithm for edge coloring planar graphs with \(\Delta\) colors
- Successive approximation in parallel graph algorithms
- On efficient parallel strong orientation
- Efficient parallel algorithms for doubly convex-bipartite graphs
- Efficient parallel graph algorithms for coarse grained multicomputers and BSP
- The parallel solution of domination problems on chordal and strongly chordal graphs
- Conditions for swappability of records in a microdata set when some marginals are fixed
- Counting clique trees and computing perfect elimination schemes in parallel
- Fast and optimal simulations between CRCW PRAMs
- Parallel computations on graphs
- Incomparability in parallel computation
- A new class of parallel algorithms for finding connected components on machines with bit-vector operations
- A parallel algorithm for the monadic unification problem
- 1-Approximation algorithm for bottleneck disjoint path matching
- The parallel complexity of elimination ordering procedures
- FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS
- PARALLEL BLOCK-FINDING USING DISTANCE MATRICES
- Sweep methods for parallel computational geometry
- Graph connectivity in log steps using label propagation
- Computation models and function algebras
- Hammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problems
- An nc algorithm to recognize hhd-free graphs
- A perfect parallel dictionary
- Efficient parallel modular decomposition (extended abstract)
- On the parallel computation of the biconnected and strongly connected co-components of graphs
- New fast parallel algorithm for the connected component problem and its VLSI implementation
- On the Strongly Connected and Biconnected Components of the Complement of Graphs
- Successive approximation in parallel graph algorithms (extended abstract)
- NC algorithms for weighted planar perfect matching and related problems
- Concurrent disjoint set union
- Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality
- On the complexity of the maximum biplanar subgraph problem
- Title not available (Why is that?)
- A simple nc algorithm to recognize weakly triangulated graphs
- Efficient algorithmic learning of the structure of permutation groups by examples
- A remark on maximum matching of line graphs
This page was built for publication: An O(logn) parallel connectivity algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3957960)
