An adaptive and cost-optimal parallel algorithm for minimum spanning trees
A parallel algorithm is described for computing the minimum spanning tree of an undirected, connected and weighted graph with n vertices. We assume a shared-memory single-instruction-stream, multiple-data-stream model of computation which does not allow read or write conflicts. The algorithm is adaptive in the sense that it uses \(n^{1-e}\) processors and runs in \(O(n^{1+e})\) time where e lies between 0 and 1 and depends on the number of available processors. In view of the obvious \(\Omega (n^ 2)\) lower bound on the number of operations required to compute a minimum spanning tree, the algorithm is also cost-optimal.
- A Parallel Algorithm for Computing Minimum Spanning Trees
- scientific article; zbMATH DE number 3956442
- Parallel Algorithms for Minimum Spanning Tree Problem
- An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem
- Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- A parallel algorithm for constructing minimum spanning trees
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Cellular arrays for the solution of graph problems
- Efficient parallel algorithms for some graph problems
- Efficient VLSI Networks for Parallel Processing Based on Orthogonal Trees
- Expected parallel time and sequential space complexity of graph and digraph problems
- Fast parallel sorting algorithms
- Fast, Efficient Parallel Algorithms for Some Graph Problems
- Graph Problems on a Mesh-Connected Processor Array
- scientific article; zbMATH DE number 3860407 (Why is no real title available?)
- scientific article; zbMATH DE number 3905859 (Why is no real title available?)
- scientific article; zbMATH DE number 3690676 (Why is no real title available?)
- Parallel algorithms for the connected components and minimal spanning tree problems
- Parallel computation and conflicts in memory access
- An efficient parallel algorithm for updating minimum spanning trees
- On the expected number of optimal and near-optimal solutions to the Euclidean travelling salesman problem. I
- An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem
- A parallel recursive shortest spanning tree algorithm for image segmentation in distributed computing environment
- scientific article; zbMATH DE number 1629846 (Why is no real title available?)
- An I/O efficient algorithm for minimum spanning trees
- Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe
- scientific article; zbMATH DE number 4011954 (Why is no real title available?)
- scientific article; zbMATH DE number 24457 (Why is no real title available?)
- On random and adaptive parallel generation of combinatorial objects
- scientific article; zbMATH DE number 1556480 (Why is no real title available?)
- Parallel Algorithms for Minimum Spanning Tree Problem
- A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
- A Parallel Algorithm for Computing Minimum Spanning Trees
- Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs
- An adaptive parallel algorithm for analyzing activity networks
This page was built for publication: An adaptive and cost-optimal parallel algorithm for minimum spanning trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1060018)
