Optimal parallel algorithms on planar graphs

DOI10.1016/0890-5401(90)90034-FzbMath0689.68056MaRDI QIDQ582094

Torben Hagerup

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

connected componentsspanning treePRAMEREW PRAMparallel graph algorithmsbiconnected componentsCRWC PRAmstrong orientation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

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 ⋮ An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs ⋮ Efficient computation of implicit representations of sparse graphs ⋮ Fast and optimal simulations between CRCW PRAMs ⋮ Improved deterministic parallel integer sorting ⋮ Parallel algorithms with optimal speedup for bounded treewidth ⋮ Efficient parallel algorithms for shortest paths in planar digraphs ⋮ A simple parallel algorithm for computing the diameters of all vertices in a tree and its application ⋮ Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On saving space in parallel computation
• Parallel construction of subdivision hierarchies
• Parallel algorithms for the connected components and minimal spanning tree problems
• Faster optimal parallel prefix sums and list ranking
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• On Synchronous Parallel Computations with Independent Probabilistic Choice
• An Efficient Parallel Biconnectivity Algorithm
• Deterministic coin tossing with applications to optimal parallel list ranking
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Relations between Concurrent-Write Models of Parallel Computation
• Parallel Symmetry-Breaking in Sparse Graphs
• Computing connected components on parallel computers
• Efficient parallel algorithms for some graph problems
• An O(logn) parallel connectivity algorithm
• Optimal Parallel 5-Colouring of Planar Graphs