## 3 Generic Algorithm to Determine Maximum Bottleneck Node Weight-Based Data Gathering Trees
### Description of the MaxBNW-DG Algorithm  
The underlying theme behind the MaxBNW-DG algorithm is to give preference for nodes with larger weights to serve as intermediate nodes. The bottleneck weight of a path between two nodes is the minimum of the weights of the nodes on the path (including those of the end nodes). Each node prefers to join the DG tree through a neighbor that has the largest bottleneck weight path to the root node. The bottleneck weight of the path that connects a node to the root node of the DG tree is referred to as the _Tree-join-weight_. We maintain three lists during the execution of the algorithm: _Candidate-Nodes-List_, _Optimized-Nodes-List_ and _Parent-Node-List_. The bottleneck path weights of the vertices in the _Candidate-Nodes-List_ are referred to as the _Estimated-join-weights_ (an estimate of the optimal bottleneck weight of the path to the root node) and when a vertex is removed from the _Candidate-Nodes-List_ and included in the _Optimized-Nodes-List_, we set its _Tree-join-weight_ to the value of the _Estimated-join-weight_ of the vertex at the time of its removal from the _Candidate-Nodes-List_. The _Candidate-Nodes-List_ is implemented as a priority queue (maximum heap) [26]. The _Parent-Node-List_ keeps track of the predecessor node for every node in the DG tree. Algorithm 1 presents the pseudo code for the MaxBNW-DG algorithm. ```
Input: Graph \(G=(V,E,W_{V},W_{E})\) Output:\(T_{Max}^{\mathit{BNW}}(V,E_{T})\) where \(E_{T}\) is the set of edges in the MaxBNW-DG tree Auxiliary Variables: Optimized-Nodes-List, Candidate-Nodes-List, Parent-Node-List Estimated-join-weight, Tree-join-weight, Leader Node Initialization: Optimized-Nodes-List = \(\phi\); Candidate-Nodes-List = \(\phi\), Parent-Node-List = \(\phi\), \(E_{T}=\phi\)\(\forall u\in V:\) Estimated-join-weight(\(u\)) = -1 \(\forall\)
```  
**Begin**_MaxBNW-DG Algorithm_  
```
1 Leader Node \(s=\{u\mid\ Maximum_{u\in V}\)(\(W_{V}(u)\))}
2 Parent-Node-List(\(s\)) = NULL
3 Candidate-Nodes-List = Candidate-Nodes-List \(\cup\){\(s\)}
4 Estimated-join-weight(\(s\)) = \(W_{i}(s)\)while(Candidate-Nodes-List \(\
eq\)\(\phi\))do
5 Node \(u=\{i\mid\ Maximum_{u\in\mathit{Candidate-Nodes-List}}\)(Estimated-join-weights(\(i\)))
7 Candidate-Nodes-List = Candidate-Nodes-List - \(\{u\}\)
8 Optimized-Nodes-List = Optimized-Nodes-List \(\cup\){\(u\)}
9 Tree-join-weight(\(u\)) = Estimated-join-weight(\(u\))
10 for( Node \(v\in Neighbors(u)\) AND \(v\
ot\in\)Optimized-Nodes-List)do
11 if(Estimated-join-weight(\(v\)) < Minimum(\(W_{i}(v)\), Tree-join-weight(\(u\)) ) ) then
12 Estimated-join-weight(\(v\)) = Minimum(\(W_{i}(v)\), Tree-join-weight(\(u\)) )
13 Parent-Node-List(\(v\)) = \(u\)
14 endif
15 endfor
16 endwhile
17 if(Candidate-Nodes-List = \(\phi\) AND \(\mid\)Optimized-Nodes-List \(\mid\)\(<\)\(\mid\)\(V\) ) then
18 return NULL; // the graph is not connected
19 endif
20 if(Candidate-Nodes-List = \(\phi\) AND \(\mid\)Optimized-Nodes-List \(\mid\)\(=\)\(\mid\)\(V\) ) then
21 for(Node \(u\in V\) AND \(u\
eq\)Leader Node )do
```  
**Algorithm 1**Pseudo Code for the Algorithm to Determine Maximum Bottleneck Node Weight-DG Trees. The algorithm proceeds in iterations; in each iteration, we explore the neighborhood (_i.e._, visit the neighbor nodes) of a vertex that currently has the largest _Estimated-join-weight_ among the vertices in the _Candidate-Nodes-List_. As part of this procedure, the vertex is also removed from the _Candidate-Nodes-List_ and added to the _Optimized-Nodes-List_; we say the vertex has been optimized (_i.e._, its _Estimated-join-weight_ cannot be further increased) and set its _Tree-join-weight_ to be its _Estimated-join-weight_ value at the time of exploring its neighbors and removal from the _Candidate-Nodes-List_. Thus, the _Optimized-Nodes-List_ includes vertices whose neighborhood has been already explored and the _Tree-join-weight_ of a vertex at the time of its inclusion in the _Optimized-Nodes-List_ is the best possible bottleneck path weight with which the node can be part of the DG tree.