An O(logn) parallel connectivity algorithm
From MaRDI portal
Publication:3957960
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
- Adapting parallel algorithms to the W-stream model, with applications to graph problems
- Finding small simple cycle separators for 2-connected planar graphs
- An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
- The parallel complexity of elimination ordering procedures
- 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
- Data reduction and fast routing: A strategy for efficient algorithms for message-passing parallel computers
- 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
- FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS
- PARALLEL BLOCK-FINDING USING DISTANCE MATRICES
- Optimal parallel algorithms on planar graphs
- Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
- Efficient parallel algorithms to test square-freeness and factorize strings
- An optimal parallel connectivity algorithm
- Sweep methods for parallel computational geometry
- Optimal parallel algorithms for multiple updates of minimum spanning trees
- Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
- A complexity theory of efficient parallel algorithms
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Graph connectivity in log steps using label propagation
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- Hammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problems
- Computation models and function algebras
- An nc algorithm to recognize hhd-free graphs
- A perfect parallel dictionary
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Efficient parallel modular decomposition (extended abstract)
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Resource bounds for parallel computation of threshold and symmetric functions
- On the parallel computation of the biconnected and strongly connected co-components of graphs
- A parallel-design distributed-implementation (PDDI) general-purpose computer
- Finding Euler tours in parallel
- Static and dynamic parallel computation of connected components
- Efficient algorithms for acyclic colorings of graphs
- New fast parallel algorithm for the connected component problem and its VLSI implementation
- Monte Carlo circuits for the abelian permutation group intersection problem
- Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
- Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays
- Parallel ear decomposition search (EDS) and st-numbering in graphs
- Separation and lower bounds for ROM and nondeterministic models of parallel computation
- GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU
- 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 the Strongly Connected and Biconnected Components of the Complement of 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
- Successive approximation in parallel graph algorithms (extended abstract)
- NC algorithms for weighted planar perfect matching and related problems
- Concurrent disjoint set union
- On efficient parallel strong orientation
- Efficient parallel algorithms for doubly convex-bipartite graphs
- Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality
- Efficient parallel graph algorithms for coarse grained multicomputers and BSP
- On the complexity of the maximum biplanar subgraph problem
- 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
- scientific article; zbMATH DE number 7561507 (Why is no real title available?)
- Efficient algorithmic learning of the structure of permutation groups by examples
- A simple nc algorithm to recognize weakly triangulated graphs
- Counting clique trees and computing perfect elimination schemes in parallel
- Fast and optimal simulations between CRCW PRAMs
- Incomparability in parallel computation
- Parallel computations on graphs
- A remark on maximum matching of line graphs
- 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
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)
