Constrained Minimum Spanning Tree (CMST) is an MST that satisfies 1 or more constraints
Example Constraints
- Any subtree rooted at a neighbor of the main root can have at most ν nodes. That is if a node A is directly connected to the main root in the tree, then the subtree (cluster) rooted at A can have altogether at most ν nodes (including A itself).
Motivation: each outgoing link from the root carries data to the group of nodes in the subtree. The larger is such a cluster, the larger is the expected data rate. The speed of the link and of the corresponding output port of the root node may limit this.
Algorithms in Computing CMST
Let us outline 3 heuristic algorithms for that last example constraint
|
Description | ||
|---|---|---|
|
Modified Kruskal’s Algorithm |
Run the original Kruskal algorithm on the nodes other than the root, but whenever a cluster arises pick its node nearest to the root and connect it directly to the root. After such a cluster is connected to the root, and there are still leftover nodes, then repeat the procedure with the leftover nodes (excluding those that already belong to a cluster) | |
|
Esau-William’s Algorithm | ||
|
Sharma El-Bardai Algorithm |