An optimal parallel algorithm for minimum spanning trees in planar graphs

DOI10.1007/978-3-319-24024-4_11MaRDI QIDQ3464472zbMATH OpenOpenAlexFDO

Authors Ka Wong Chong, Christos 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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• A Parallel Algorithm for Computing Minimum Spanning Trees
• An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem
• Optimal parallel algorithms on planar graphs
• A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
• Improving the efficiency of parallel minimum spanning tree algorithms

Cites work

• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• A Parallel Algorithm for Computing Minimum Spanning Trees
• A randomized linear-time algorithm to find minimum spanning trees
• A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
• An optimal minimum spanning tree algorithm
• Concurrent threads and optimal parallel minimum spanning trees algorithm
• Deterministic coin tossing with applications to optimal parallel list ranking
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Efficient parallel algorithms for some graph problems
• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• Finding Minimum Spanning Trees
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• Optimal Parallel 5-Colouring of Planar Graphs
• Optimal parallel algorithms on planar graphs
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Parallel Symmetry-Breaking in Sparse Graphs
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths

Cited in

(19)

• Parallel algorithms for finding the most vital edge with respect to minimum spanning tree
• An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• A randomized linear-work EREW PRAM algorithm to find a minimum spanning forest
• The minimum spanning tree problem on a planar graph
• Improving the efficiency of parallel minimum spanning tree algorithms
• Parallel algorithm for minimum partial dominating set in unit disk graph
• Optimal parallel verification of minimum spanning trees in logarithmic time
• scientific article; zbMATH DE number 1629846 (Why is no real title available?)
• An optimal EREW PRAM algorithm for minimum spanning tree verification
• A data-parallel algorithm for minimum-width tree layout
• Two linear time algorithms for MST on minor closed graph classes.
• Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe
• scientific article; zbMATH DE number 3980506 (Why is no real title available?)
• scientific article; zbMATH DE number 4060742 (Why is no real title available?)
• scientific article; zbMATH DE number 1161295 (Why is no real title available?)
• A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
• Parallel algorithms for geometric graph problems
• Optimal parallel algorithms on planar graphs

This page was built for publication: An optimal parallel algorithm for minimum spanning trees in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3464472)