A Decentralized Algorithm for Finding the Shortest Paths in Defense Communications Networks.

Abstract

This paper presents a decentralized shortest path algorithm which finds the shortest distances between all pairs of nodes without requiring that any particular node have information about the complete topology of the network. The algorithm requires at most N3/2 additions, N3/2 comparisons, and N3/2 transmissions of simple message between individual nodes. The computational upper bound of the present algorithm is lower than that of Dijkstra's centralized shortest path algorithm and is 1/N of the upper bound of Abram and Rhodes' decentralized shortest path algorithm. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1979
Accession Number
ADA074381

Entities

People

  • Jin Y. Yen

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Buildings And Structures
  • Communication Networks
  • Computations
  • Determinants (Mathematics)
  • Marine Corps
  • Military Research
  • National Security
  • Network Topology
  • Networks
  • Operations Research
  • Security
  • Space Systems
  • Test And Evaluation
  • Timing Devices

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.