A parallel algorithm for constructing minimum spanning trees

DOI10.1016/0196-6774(80)90004-8zbMath0435.68049OpenAlexW2012667106MaRDI QIDQ3875355

Jon Louis Bentley

Publication date: 1980

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(80)90004-8

zbMATH Keywords

parallel algorithmminimum spanning trees of weighted graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (16)

An introduction to parallelism in combinatorial optimization ⋮ An O(N log N) minimal spanning tree algorithm for N points in the plane ⋮ A fully distributed (minimal) spanning tree algorithm ⋮ A massively parallel algorithm based on DNA computations for constructing minimal spanning trees ⋮ Finding fundamental cycles and bridges on a tree-structured parallel computer ⋮ Parallel computations on graphs ⋮ Synchronization coherence: a transparent hardware mechanism for cache coherence and fine-grained synchronization ⋮ Parallel algorithms for the single source shortest path problem ⋮ Stirling networks: A versatile combinatorial topology for multiprocessor systems ⋮ Parallel algorithm for analysing activity networks on a tree-structured computer ⋮ An Event-Driven Algorithm for Agents on the Web ⋮ Computing with pipelined block transfer ⋮ Unbounded hardware is equivalent to deterministic Turing machines ⋮ Graph algorithms on a tree-structured parallel computer ⋮ An adaptive and cost-optimal parallel algorithm for minimum spanning trees ⋮ A model of sequential computation with Pipelined access to memory

This page was built for publication: A parallel algorithm for constructing minimum spanning trees