Contact: Eric Gauthier
The goal of the project is to program an exhaustive algorithm to compute the shortest tree that spans a given subset of nodes in a network, called the terminals. The proposed algorithm consists of computing the minimum spanning tree of all subsets of nodes in the network that contain all terminals. The implementation should be performed in the Stanford Graph Base and use the Kruskal algorithm implemented in MILES_SPAN. The correctness of the implementation should be tested on well known cases. The performance of the algorithm should be tested on random graphs. If time permits preprocessing of the input data should be implemented.
Benefits:
- design an algorithm to generate all the subsets of nodes in the graph that contain the terminals
- implementation of the algorithm
- correctness assessment
- performance evaluation
Domain:
Protocol design and implementation
Student info:
Frederic Pont