Computing Minimum Spanning Trees on a Fat-Tree Architecture.

Abstract

This paper presents two parallel algorithms for computing the minimum spanning forest of an input graph on a fat-tree architecture. One algorithms if deterministic, and the other probabilistic. The deterministic algorithm generates O(cv log/V/) message sets, each of which can be delivered in O(beta (G) delivery cycles. The probabilistic algorithm generates O(sq log/V/) message sets, each of which can be delivered in O(beta(G)) delivery cycles. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1985
Accession Number
ADA161434

Entities

People

  • Bruce M. Maggs

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Broadcasting
  • Channel Capacity
  • Communication Channels
  • Computer Science
  • Computers
  • Construction
  • Electrical Engineering
  • Engineering
  • Identities
  • Instructions
  • Iterations
  • Massachusetts
  • Probability
  • Transitions
  • Trees (Data Structures)

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.
  • Rehabilitation and Prosthetic Care for Military Service Members and Veterans with Limb Loss or Disability.