An Efficient Parallel Biconnectivity Algorithm
From MaRDI portal
Publication:3694710
DOI10.1137/0214061zbMath0575.68066WikidataQ55966916 ScholiaQ55966916MaRDI QIDQ3694710
Robert Endre Tarjan, Uzi Vishkin
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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C40: Connectivity
Related Items
Optimal parallel colouring algorithms for totally decomposable graphs, An optimal parallel algorithm for computing cut vertices and blocks on interval graphs, An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs, Solving the shortest-paths problem on bipartite permutation graphs efficiently, Optimal parallel algorithms for path problems on planar graphs, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, Efficient parallel term matching and anti-unification, A unified approach to parallel depth-first traversals of general trees, Planar orientations with low out-degree and compaction of adjacency matrices, Efficient algorithms for the minimum weighted dominating clique problem on permutation 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, 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, 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, Sorting in linear time?, More general parallel tree contraction: Register allocation and broadcasting in a tree, On testing consecutive-ones property in parallel, Parallel construction and query of index data structures for pattern matching on square matrices, 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, 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, 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, Planarity testing in parallel, Efficient parallel recognition algorithms of cographs and distance hereditary graphs, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm, A remark on maximum matching of line graphs, An optimal parallel algorithm for digital curve segmentation, Computing Prüfer codes efficiently in parallel, Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree, An efficient distributed bridge-finding algorithm, Optimal parallel algorithms for rectilinear link-distance problems, Sweep methods for parallel computational geometry, Optimal computation of shortest paths on doubly convex bipartite graphs, Efficient algorithms for acyclic colorings of graphs, Optimal parallel algorithms for multiple updates of minimum spanning trees, Selecting distances in the plane, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS
