An O(logn) parallel connectivity algorithm
From MaRDI portal
Publication:3957960
DOI10.1016/0196-6774(82)90008-6zbMath0494.68070OpenAlexW2004350101WikidataQ56813859 ScholiaQ56813859MaRDI QIDQ3957960
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)
Related Items
A new class of parallel algorithms for finding connected components on machines with bit-vector operations, A parallel algorithm for computing Steiner trees in strongly chordal graphs, The parallel solution of domination problems on chordal and strongly chordal graphs, On efficient parallel strong orientation, A parallel algorithm for the monadic unification problem, Optimal parallel algorithms for multiple updates of minimum spanning trees, Finding small simple cycle separators for 2-connected planar graphs, Incomplete directed perfect phylogeny in linear time, Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Efficient parallel recognition algorithms of cographs and distance hereditary graphs, Parallel ear decomposition search (EDS) and st-numbering in graphs, Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, \(O(\log \log n)\)-time integer geometry on the CRCW PRAM, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Separation and lower bounds for ROM and nondeterministic models of parallel computation, On the parallel computation of the biconnected and strongly connected co-components of graphs, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, Communication-efficient parallel algorithms for distributed random-access machines, GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU, Chordal graph recognition is in NC, FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS, PARALLEL BLOCK-FINDING USING DISTANCE MATRICES, A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs, Sweep methods for parallel computational geometry, Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs, Parallel computational geometry, Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs, An nc algorithm to recognize hhd-free graphs, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Efficient parallel graph algorithms for coarse grained multicomputers and BSP, A remark on maximum matching of line graphs, NC Algorithms for Weighted Planar Perfect Matching and Related Problems, A linear systolic algorithm for the connected component problem, A parallel algorithm for the maximum 2-chain edge packing problem, Graph Connectivity in Log Steps Using Label Propagation, Fast and optimal simulations between CRCW PRAMs, A perfect parallel dictionary, Parallel computations on graphs, Computation models and function algebras, Adapting parallel algorithms to the W-stream model, with applications to graph problems, Efficient parallel modular decomposition (extended abstract), The parallel complexity of elimination ordering procedures, Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality, A parallel algorithm for eliminating cycles in undirected graphs, Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs, A complexity theory of efficient parallel algorithms, Successive approximation in parallel graph algorithms, An efficient algorithm for edge coloring planar graphs with \(\Delta\) colors, Incomparability in parallel computation, Efficient algorithmic learning of the structure of permutation groups by examples, Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays, Efficient parallel algorithms to test square-freeness and factorize strings, Efficient algorithms for acyclic colorings of graphs, Processor-time tradeoffs in PRAM simulations, Data reduction and fast routing: A strategy for efficient algorithms for message-passing parallel computers, Efficient parallel algorithms for doubly convex-bipartite graphs, 1-Approximation algorithm for bottleneck disjoint path matching, Fast connected-component labeling, On the complexity of the maximum biplanar subgraph problem, Conditions for swappability of records in a microdata set when some marginals are fixed, Unnamed Item, Optimal parallel algorithms on planar graphs, New fast parallel algorithm for the connected component problem and its VLSI implementation, Counting clique trees and computing perfect elimination schemes in parallel, On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs, Successive approximation in parallel graph algorithms, Resource bounds for parallel computation of threshold and symmetric functions, Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, Concurrent disjoint set union, Monte Carlo circuits for the abelian permutation group intersection problem, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Vectorized search for single clusters, A simple nc algorithm to recognize weakly triangulated graphs, A parallel-design distributed-implementation (PDDI) general-purpose computer, An optimal parallel connectivity algorithm, Finding Euler tours in parallel, On the Strongly Connected and Biconnected Components of the Complement of Graphs, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, Static and dynamic parallel computation of connected components
