An O(log n) Time Common CRCW Pram Algorithm for Minimum Spanning Tree.

Abstract

The Minimum Spanning Tree problem is an important problem of combinatorial optimization. Some practical applications of MST's include the design of computer, communication, and transportation networks. Graham and Hell gave an extensive history of the MST problem. Yao and Cheriton and Tarjan designed sequential MST algorithms that ran in time O(m log log n). Awerbuch presented an optimal distributed MST algorithm that requires O(m+n log n) messages and O(n) time. There have also been several parallel MST algorithms. In this paper, we employ some of the results of Fich et al. 7 and modify Awerbuch and Shiloach's algorithm to obtain a Common CRCW PRAM MST algorithm. Keywords: Computations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1990
Accession Number
ADA228740

Entities

People

  • Michael M. Wu

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computational Science
  • Computations
  • Computers
  • Contracts
  • Engineering
  • Flow Network
  • Graphs
  • Illinois
  • Iterations
  • Mathematics
  • Military Research
  • Security
  • Universities

Readers

  • Astronomy and Astrophysics.
  • Graph Algorithms and Convex Optimization.