An Efficient Parallel Biconnectivity Algorithm
From MaRDI portal
Publication:3694710
DOI10.1137/0214061zbMath0575.68066OpenAlexW1995040285WikidataQ55966916 ScholiaQ55966916MaRDI QIDQ3694710
Uzi Vishkin, Robert Endre Tarjan
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0214061
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Related Items
Parallel algorithms for all minimum link paths and link center problems, Fully dynamic 2-edge-connectivity in planar graphs, Computing the all-pairs longest chains in the plane, AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS, FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS, A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS∗, PARALLEL BLOCK-FINDING USING DISTANCE MATRICES, The parallel complexity of tree embedding problems (extended abstract), Partitioning into degenerate graphs in linear time, Time-optimal construction of overlay networks, Efficient parallel modular decomposition (extended abstract), The parallel complexity of elimination ordering procedures, DFS tree construction: Algorithms and characterizations, Listing all spanning trees in Halin graphs — sequential and Parallel view, Two faces of greedy leaf removal procedure on graphs, COLORING ALGORITHMS ON SUBCUBIC GRAPHS, Parallelism and dictionary based data compression, ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS, Unnamed Item, An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs, Successive approximation in parallel graph algorithms, A theory of strict P-completeness, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS, New algorithms for the LCA problem and the binary tree reconstruction problem, Finding level-ancestors in trees, An efficient parallel algorithm for the single function coarsest partition problem, A parallel algorithm for computing Steiner trees in strongly chordal graphs, The parallel solution of domination problems on chordal and strongly chordal graphs, Data structures for two-edge connectivity in planar graphs, On efficient parallel strong orientation, Optimal parallel algorithms for multiple updates of minimum spanning trees, Selecting distances in the plane, An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs, An optimal EREW PRAM algorithm for minimum spanning tree verification, Smallest bipartite bridge-connectivity augmentation, A parallel algorithm for finding a triconnected component separator with an application, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Prallel algorithms for analyzing activity networks, Planarity testing in parallel, Efficient parallel recognition algorithms of cographs and distance hereditary graphs, Parallel ear decomposition search (EDS) and st-numbering in graphs, On the complexity of parallel parsing of general context-free languages, An efficient distributed bridge-finding algorithm, Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees, Optimal parallel algorithms for rectilinear link-distance problems, 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, Parallel algorithms for shortest path problems in polygons, The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time, Parallel O(log n) time edge-colouring of trees and Halin graphs, A 2-approximation NC algorithm for connected vertex cover and tree cover, A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs, Sweep methods for parallel computational geometry, A linear-processor algorithm for depth-first search in planar graphs, Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs, Parallel computational geometry, Concurrent vs. exclusive reading in parallel decoding of LZ-compressed files, Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm, Efficient parallel graph algorithms for coarse grained multicomputers and BSP, A remark on maximum matching of line graphs, An optimal parallel algorithm for the minimum circle-cover problem, Data-Oblivious Graph Algorithms in Outsourced External Memory, An optimal parallel algorithm for digital curve segmentation, Optimal parallel colouring algorithms for totally decomposable graphs, A time-optimal solution for the path cover problem on cographs., Scalability and communication in parallel low-complexity lossless compression, Optimally edge-colouring outerplanar graphs is in NC, A simple randomized parallel algorithm for list-ranking, Parallel construction of minimal suffix and factor automata, Successive approximation in parallel graph algorithms, Priority functions for the approximation of the metric TSP, Subtree isomorphism is in random NC, Optimal computation of shortest paths on doubly convex bipartite graphs, A unified approach to parallel depth-first traversals of general trees, Planar orientations with low out-degree and compaction of adjacency matrices, Distributed hierarchical search for balanced energy consumption routing spanning trees in wireless sensor networks, Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs, Efficient algorithms for acyclic colorings of graphs, Breadth-first traversal of trees and integer sorting in parallel, Optimal parallel algorithms for forest and term matching, Maintaining bridge-connected and biconnected components on-line, Efficient parallel algorithms for path problems in directed graphs, A model classifying algorithms as inherently sequential with applications to graph searching, Solving the shortest-paths problem on bipartite permutation graphs efficiently, Optimal parallel algorithms for path problems on planar graphs, Parallel rectilinear shortest paths with rectangular obstacles, A new graph triconnectivity algorithm and its parallelization, Optimal parallel algorithms for finding cut vertices and bridges of interval graphs, A simple parallel algorithm for computing the diameters of all vertices in a tree and its application, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, Efficient parallel term matching and anti-unification, Tight complexity bounds for term matching problems, Parallel methods for visibility and shortest-path problems in simple polygons, Parallel search algorithms for graphs and trees, An optimal parallel algorithm for computing furthest neighbors in a tree, The bridge-connectivity augmentation problem with a partition constraint, Optimal parallel algorithms on planar graphs, Efficient parallel algorithms for r-dominating set and p-center problems on trees, A parallel algorithm for finding a blocking flow in an acyclic network, Optimal parallel algorithms on circular-arc graphs, The Monotone Circuit Value Problem with Bounded Genus Is in NC, Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree, Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, Sorting in linear time?, More general parallel tree contraction: Register allocation and broadcasting in a tree, Computing Prüfer codes efficiently in parallel, Solving some combinatorial problems on arrays with one-way dataflow, On testing consecutive-ones property in parallel, Faster optimal parallel prefix sums and list ranking, Parallel construction and query of index data structures for pattern matching on square matrices, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, An optimal parallel algorithm for computing cut vertices and blocks on interval graphs, A parallel-design distributed-implementation (PDDI) general-purpose computer, An optimal parallel connectivity algorithm, Parallel preprocessing for path queries without concurrent reading., Finding Euler tours in parallel, Solving NP-hard problems in 'almost trees': vertex cover, Improving the efficiency of parallel minimum spanning tree algorithms, Improved algorithms for graph four-connectivity, Deterministic parallel list ranking, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, Recognition algorithm for intersection graphs of edge disjoint paths in a tree, Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
