## 2 Materials and Methods
### Random Tree Pruning Based Search
Because the size of the tree of mutually acceptable interfering line sets grows exponentially (Figure 10a), we stopped the experiments with the complete tree at 60 nodes. The larger the pruning scale factor, the closer the results are to the complete tree case. Specifically, the results of the genetic algorithm with scale factor 4 are quite similar to the complete tree. The difference between results for scale factors 2 and 4 is less than between scale factors 1 and 2. The stopping criterion for the genetic algorithm and random search is the sliding maximum number of iterations, which is 2 times larger than the last best solution improvement iteration. In addition, we forced the minimum number of 20 iterations. Figure 10c shows the mean number of iterations. Random search stops slightly above the minimal number of iterations regardless of the number of nodes. The genetic algorithm improves the solution for a larger number of iterations. The number of iterations for the genetic algorithm grows with the number of nodes. We see that, with smaller trees (smaller pruning scale factor), the genetic algorithm takes much more iterations to stop. The time complexity is shown in Figure 10b. It grows proportionally with increase in space complexity. Time complexity is the highest for the genetic algorithm: we stopped the experiments with the genetic algorithm at 100 nodes. Despite the variety of pruning scale factors, the time complexity of the genetic algorithm differs slightly due to a very different number of iterations. The fastest and simplest way is to use random search. Its cost function is close to the genetic algorithm with the growing number of nodes. Our proposed algorithm only mitigates the combinatorial explosion but does not eliminate it. To model the extremely large-scale scenario (tens of thousands, hundreds of thousands, or millions of nodes), we will, eventually, need some high-performance computing cluster or even a supercomputer. To make our algorithm even more scalable, we have to, with some heuristic, generate the multiple partitions of line sets and apply our proposed algorithm to each partition. Even though we partition, we still consider the global interference without localizing it. In the case of line partitioning, the minimal achievable number of resources is equal to the number of line partitions. We now have the optimization problem with two optimization spaces: the number of partitions and the partitioning composition itself. With this optimization, we can eventually stumble upon the same resource assignment solution as if we had applied our algorithm directly to theextremely large number of nodes. The case with only the partition of the lines reduces the aforementioned optimization into our proposed algorithm. The experiments were conducted with the AWGN interference model, free-space propagation model, and uniform node distribution. But there can be many other cases of node distributions, interference, and space propagation models. The worst time complexity for mutual interference estimation still depends on the number of lines in the set irrespective of the interference and propagation models. We need to mention the mutual pairwise interference limitation. We assume that if one or both lines exceed the interference thresholds of each other, then adding another line to the pair will make the interference worse. Hence, our proposed algorithm is not applicable in the case of constructive interference. An example of constructive interference is cooperative beamforming, when multiple nodes transmit the same packet to one node to enhance the resulting SNR. As for the node distribution, lots of \"clumped\" together nodes would not be able to transmit together either due to a simplex restriction or due to mutual pairwise interference exceeding the threshold. Thus, tree construction will be much faster.