
Modeling and Simulation Tools for Mobile Ad Hoc Networks ◾ 47
A minimum spanning tree (MST) for a graph is a subgraph that has the minimum edge weight for
maintaining connectivity. A sample MANET and an MST constructed can be seen in Figure 3.11a
and b, respectively. In Figure 3.11b, any nodes, other than the leaf nodes, that are shown by black
color depict a connected set of nodes.
Gallager et al. [15] proposed a distributed algorithm that determines a minimum weight span-
ning tree for a UG that has distinct finite weights for every edge. e aim of this algorithm is to
combine small fragments into larger fragments with outgoing edges. A fra ...