/finding_eccentricities

A distributed algorithm for finding eccentricities in a tree

Primary LanguageCMIT LicenseMIT

Distributed Processing - Algorithms on trees

Description

Finding eccentricities in a tree

Eccentricity of a tree image

Image taken from Wolfram MathWorld.

Implementation

The is a distributed algorithm implemented in C with MPI. It uses the saturation method to get a complexity of O(n). It has 3 stages:

  1. Activation
  2. Saturation
  3. Resolution

These are represented in the following image:

Saturation method image

Documentation

See Documentation for mode details.

References

The algorithm is implemented from N. Santoro, Design and Analysis of Distributed Algorithms, Ottawa: WILEY-INTERSCIENCE, 2006.

License

The application is licensed under the MIT License.