A simple parallel tree contraction algorithm
From MaRDI portal
Publication:4730794
DOI10.1016/0196-6774(89)90017-5zbMath0681.68085OpenAlexW1965874601MaRDI QIDQ4730794
No author found.
Publication date: 1989
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(89)90017-5
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
The parallel solution of domination problems on chordal and strongly chordal graphs, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, Parallel algorithm for finding a core of a tree network, Local consistency in parallel constraint satisfaction networks, An optimal parallel algorithm forc-vertex-ranking of trees, A faster parallel connectivity algorithm on cographs, Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs, An efficient parallel algorithm for finding rectangular duals of plane triangular graphs, Parallel tree contraction and prefix computations on a large family of interconnection topologies, Efficient parallel algorithms for shortest paths in planar graphs, Parallel algorithm for cograph recognition with applications, Parallel maximum independent set in convex bipartite graphs, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Improved parallel depth-first search in undirected planar graphs, An optimal parallel algorithm for planar cycle separators, THE OPTIMAL LOCATION OF A STRUCTURED FACILITY IN A TREE NETWORK, AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS, Sweep methods for parallel computational geometry, Parallel evaluation of arithmetic circuits, An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs, A note on parallel algorithms for optimal h-v drawings of binary trees, Parallel approximation schemes for problems on planar graphs, Parallel algorithms for the minimum cut and the minimum length tree layout problems, Efficient parallel algorithms for some tree layout problems, Optimal parallel colouring algorithms for totally decomposable graphs, A time-optimal solution for the path cover problem on cographs., On parallel recognition of cographs, Parallel algorithms for fractional and maximal independent sets in planar graphs, Parallel recognition of complement reducible graphs and cotree construction, The Optimal Alphabetic Tree problem revisited, A parallel tree difference algorithm, Parallel algorithms with optimal speedup for bounded treewidth, A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles, Deciding whether graph \(G\) has page number one is in NC, Efficient parallel algorithms for shortest paths in planar digraphs, An O(\(n\)) time algorithm for maximum matching on cographs, Parallel methods for visibility and shortest-path problems in simple polygons, Matching parentheses in parallel, Efficiently parallelizable problems on a class of decomposable graphs, The Hamiltonian problem on distance-hereditary graphs, Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\), Efficient parallel algorithms for r-dominating set and p-center problems on trees, Optimal parallel quicksort on EREW PRAM, Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree, More general parallel tree contraction: Register allocation and broadcasting in a tree, Computing Prüfer codes efficiently in parallel, Parallel preprocessing for path queries without concurrent reading., A linear time algorithm for the maximum matching problem on cographs, On optimal parallel computations for sequences of brackets, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction, Visibility with a moving point of view
