Communication Complexity of Distributed Shortest Path Algorithms

Abstract

A new distributed shortest path algorithm for an asynchronous communication network with unit edges, of the number of elementary messages used in finding shortest paths form a given root to all other nodes is 0(V1.6+E) where V is the number of nodes and E the number of edges. For dense networks, with E > or = V to 1.6 power, this order of complexity is optimum.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1985
Accession Number
ADA156049

Entities

People

  • B. Awerbuch
  • R. G. Gallager

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Communication Channels
  • Communication Networks
  • Computations
  • Computer Networks
  • Computer Science
  • Electrical Engineering
  • Electronics Laboratories
  • Freezing
  • Information Processing
  • Information Systems
  • Iterations
  • Military Research
  • Network Protocols
  • Network Topology
  • Networks
  • Virginia

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.
  • Operations Research