A Distributed Algorithm for Minimum Weight Directed Spanning Trees

Abstract

A distributed algorithm is presented to construct minimum weight directed spanning trees (arborescences), each with a distinct root node, in a strongly connected directed graph. A processor exists at each node. Given the weights and origins of the edges incoming to its node, a processor follows the algorithm and exchanges messages with its neighbors until all arborescences are constructed. The amount of information exchanged and the time to completion are O(Absolute value of N squared).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1981
Accession Number
ADA107462

Entities

People

  • Pierre A. Humblet

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Networks
  • Cost Analysis
  • Costs
  • Electronics Laboratories
  • Identities
  • Information Processing
  • Information Systems
  • Marine Corps
  • Mathematics
  • Military Research
  • Network Topology
  • Networks
  • New York
  • Observation
  • Virginia

Readers

  • Approximation Theory.
  • Computer Networking
  • Manufacturing Engineering.