A Distributed Algorithm for Minimum Weight Spanning Trees. Revision

Abstract

A distributed algorithm is presented that constructs the minimum weight spanning tree in a connected undirected graph with distinct edge weights. A processor exists at each node of the graph, knowing initially only the weights of the adjacent edges. The processors obey the same algorithm and exchange messages with neighbors until the tree is constructed. The total number of messages required for a graph of N nodes and E edges is at most 5N log of N to the base 2 + 2E and a message contains at most one edge weight plus log of 8N to the base 2 bits. The algorithm can be initiated spontaneously at any node or at any subset of nodes.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1979
Accession Number
ADA080902

Entities

People

  • P. A. Humblet
  • P. M. Spira
  • R. G. Gallager

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Communication Networks
  • Cost Analysis
  • Costs
  • Guarantees
  • Identities
  • Materials
  • Mathematics
  • Mesh Networks
  • Networks
  • Probability
  • Rejection
  • Sequences

Readers

  • Computer Vision.
  • Parallel and Distributed Computing.
  • Regression Analysis.