# Broadcasting in Stars of Cliques and Path-Connected Cliques +
## 4 Decision Algorithm for the Broadcast Time of Star of Cliques
### Broadcasting from the Universal Vertex \(u\)  
Algorithm 3, StarOfCliquesBroadcast(\(CS\), \(t\)), determines whether broadcasting in a given star of cliques from the universal vertex \(u\) can be completed within \(t\) time units. The algorithm returns _True_ if the broadcast is feasible within the given time frame and _False_ otherwise. **Definition 1**. : _Unaddressed Vertices: When a vertex in some clique \(C_{p}\) is informed at time \(j\), this vertex becomes the root of a binomial tree \(B_{t-j}\) within \(C_{p}\). The vertices in \(B_{t-j}\) are guaranteed to be informed at or before time \(t\). All uninformed vertices in \(C_{p}\) that do not belong to such a binomial tree are called unaddressed vertices._  
In the algorithm StarOfCliquesBroadcast(\(CS\), \(t\)), the first step is to check whether vertex \(u\) needs to inform an unaddressed vertex in \(C_{1}\) during the current time unit, i.e., if \(CS[1][1]=1\). If this condition holds, it implies that \(l_{1}\geq 2^{t-j}\). In this case, \(u\) cannot inform any other clique in the current time unit, as doing so would prevent \(C_{1}\) from completing its broadcast. This is because \(l_{1}\geq 2^{t-j}>2^{t-j+1}+2^{t-j+2}+\ldots+2^{1}+2^{0}\), and the deficit in vertices cannot be compensated. However, if \(CS[2][1]=1\) simultaneously, a conflict arises, and the algorithm returns _False_. It is important to note that it is sufficient to check only \(CS[2]\) for conflicts, as the array is sorted in descending order, and all subsequent cliques \(C_{3}\ldots C_{k}\) are no larger than \(C_{2}\). On the other hand, if \(CS[1][1]\
eq 1\), this indicates that no clique requires broadcasting during the current time unit. Rather than leaving \(u\) idle, the algorithm opts to broadcast to \(C_{1}\) anyway, ensuring that \(C_{1}\) no longer needs to be informed in the future, which may help avoid conflicts in subsequent iterations. In either scenario, the algorithm proceeds by informing an unaddressed vertex in \(C_{1}\). ```
1:procedureStarOfCliquesBroadcast(\(CS\), \(t\))
2:if\(CS[1][1]==\)\"1\"then
3:if\(CS\).length\(>1\)and\(CS[2][1]==\)\"1\"then
4:return False
5:endif
6:else
7:\(s\gets 1+\underbrace{0\ldots 0}_{t-1}\)
8:endif
9:if\(t==1\)then
10:return\(True\)
11:else
12:for\(i\gets 1\) to \(k\)do
13:\(CS[i]\leftarrow\) substring\((CS[i],2,t)\)
14:endfor
15:\(CS\).sort()
16:returnStarOfCliquesBroadcast(\(CS\), \(t-1\))
17:endif
18:endprocedure
```  
**Algorithm 3** Decision algorithm for broadcasting in star of cliques from the universal vertex \(u\) in \(t\) time units. (_Note:_ Arrays are indexed starting from 1)  
The next step involves recursively calling StarOfCliquesBroadcast(\(CS\), \(t-1\)) for the next iteration. Here, \(CS[i]\) is updated to \(CS[i][2\ldots t]\), meaning the first bit, which corresponds to the now-elapsed time unit, is removed from each binary string. The algorithm continues this process until one of two conditions is met: either two cliques require broadcasting in the same time unit, resulting in the algorithm returning _False_, or the final time unit is reached, in which case the algorithm returns _True_. Complexity Analysis  
The StarOfCliquesBroadcast algorithm performs several operations whose complexities contribute to the overall runtime. Step 7 takes \(O(t)\) time to update a string if the corresponding clique is informed early. In Step 13, deleting the first bit of the \(k\) strings incurs \(O(k\cdot t)\) time. Since only the first element of the array is out of place in Step 15, the sorted array can be obtained through a single iteration of insertion sort in \(O(k)\) time. Thus, a single iteration of the algorithm requires \(O(k\cdot t)\) time. The algorithm is executed \(t\) times, leading to a cumulative complexity of \(O(k\cdot t^{2})\) time. In addition, computing the upper bound \(t^{\prime}\) requires \(O(k\cdot\log k)\) time, while generating the binary strings for all cliques takes \(O(k\cdot\log l_{1})\) time.