An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs
From MaRDI portal
Publication:3464472
DOI10.1007/978-3-319-24024-4_11zbMath1331.68283OpenAlexW1828874726MaRDI QIDQ3464472
Ka Wong Chong, Christos D. Zaroliagis
Publication date: 27 January 2016
Published in: Algorithms, Probability, Networks, and Games (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-24024-4_11
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal parallel algorithms on planar graphs
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- An optimal minimum spanning tree algorithm
- Deterministic coin tossing with applications to optimal parallel list ranking
- New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
- Parallel Symmetry-Breaking in Sparse Graphs
- Efficient parallel algorithms for some graph problems
- Finding Minimum Spanning Trees
- Optimal Parallel 5-Colouring of Planar Graphs
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- A randomized linear-time algorithm to find minimum spanning trees
- Concurrent threads and optimal parallel minimum spanning trees algorithm
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
- Finding Connected Components in O(log n log log n) Time on the EREW PRAM
- A Parallel Algorithm for Computing Minimum Spanning Trees
