## 2 Materials and Methods
### Random Tree Pruning Based Search
The number of all line sets is the number of permutations for the binary sequence of size \(N\) without a full zero sequence (empty line set). This number is equal to \(2^{N}-1\). The worst case for full tree construction is when all lines can coexist together, when we need to check all of the line sets. So, considering that the size of one set cannot be greater than \(N\), the worst case of space complexity for the construction of the full tree is \(O((2^{N}-1)\cdot N)\approx O(2^{N}\cdot N)\). The time complexity of checking mutual interference inside one set cannot be larger than \(N\cdot(N-1)\), so the worst-case time complexity is \(O(2^{N}\cdot N\cdot(N-1))\approx O(2^{N}\cdot N^{2})\). With pruning, the number of sets cannot exceed the product of the maximum number of layers (it is equal to the number of lines N) multiplied by the maximum number of nodes per layer (it is equal to the number of lines multiplied by the scale factor \(K\to N\cdot K\)): \(N\cdot N\cdot K=N^{2}\cdot K\). As stated previously, the size of the set cannot be greater than \(N\), so the worst space complexity cannot exceed \(O(N^{2}\cdot K\cdot N)\approx O(N^{3})\). We have omitted the scale factor \(K\), because it is constant. With pruned trees, we create multiple trees, the quantity of which can be constant too; so for the complexity estimation, the number of iterations can be omitted too. Before pruning, we need to create all the nodes of children in the current layer, the maximal possible number of children is \(N-1\), and the maximum time complexity to estimate sets for mutual interference cannot be greater than \(N\cdot(N-1)\), so the worst time complexity for pruned trees is \(O(N^{2}\cdot(N-1)\cdot N\cdot(N-1))\approx O(N^{5})\). Let us propose a naive greedy search algorithm for mutually acceptable interfering line sets and estimate its worst space and time complexity. We start with the first line and check sequentially for all other lines if they are interfering acceptably. If, for example, the second line is interfering acceptably, we add it to the line set. Afterwards we check for the set of two lines, if we can add line number 3, and so on. We exclude the found set from the line set. For the remaining line set, beginning from the first line, we repeat the same process until no lines are remaining. The worst case is when all lines can coexist together; we check \(N-1\) line sets with sizes from 2 to \(N\). The worst case time complexity for this case is \(O((N-1)\cdot N\cdot(N-1))\approx O(N^{3})\). If in the first iteration we obtain the set which does not include all lines, we work with the smaller \(N\) values on subsequent iterations which sum up to N. Assuming that \(\forall P,Q,N,\sigma\in\mathbb{N}:P+Q=N\implies P^{\sigma}+Q^{\sigma}<N^{\sigma}\), the worst time complexity of greedy search cannot exceed \(O(N^{3})\). Line set size cannot be \begin{table}
\begin{tabular}{c c c} \hline \hline
**Algorithm** & **Worst Space Complexity** & **Worst Time Complexity** \\ \hline Full tree & \(O(2^{N}\cdot N)\) & \(O(2^{N}\cdot N^{2})\) \\ Pruned tree & \(O(N^{3})\) & \(O(N^{5})\) \\ Greedy search & \(O(N^{2})\) & \(O(N^{3})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Worst time and space complexities for the search with full tree construction, pruned tree construction, and greedy search. greater than \(N\). The number of line sets in the proposed greedy search also cannot exceed N (the case when all lines can transmit only separately from each other). So, the worst space complexity of greedy search is \(O(N^{2})\). At the same time, greedy search does not provide optimal or even suboptimal solution in most cases. Worst-case complexities are presented on the Table 2. As we can see, tree pruning, compared to the full tree, shifts complexity from the exponential to the polynomial one, which is a quite substantial complexity reduction. ### Parallelization Considerations

Parallelization is the availability of independent computations.