## 2 Materials and Methods
### Random Tree Pruning Based Search
We can obtain better results if we sequentially optimize pruning data for each layer by evolving the population multiple times and increasing the deepest equal layer. To do that we use the following cycle of the genetic algorithm (Algorithm 4):```
1: Perform one layer evolution. 2: Take the best solution (the solution with the smallest minimal set cover). 3:if (the number of nodes of the next after the current deepest equal layer \(\leq\) the allowed number of nodes after pruning) then
4: Exit. 5:endif
6: Create the set \(S\) of \(N\) (\(N\) is the population size) empty solutions. 7:for i = 0 to \(N-2\)
8:\(S[i]\leftarrow\) create mutated copy of the best solution after the current deepest equal layer plus one. 9:endfor
10:\(S[N-1]\leftarrow\) best solution. 11:goto perform one layer evolution. ```

**Algorithm 4**Algorithm of the genetic algorithm cycle

The iteration of one layer tree evolution is described in Algorithm 5:

```
1: Randomly split the current population into pairs. 2: Perform the crossover between pairs and the mutation of resulting offsprings. 3: Find the minimal set cover for every tree in the offsprings set. 4: Unite the current population and offspring population into one population. 5: Sort the united population in the rising order of minimal set cover size. 6: Take the best, first, and half of the united population into the next population. 7: Find the tree with the smallest minimal set cover among the new population. It is the first tree in the population, as we previously sorted the population. 8:if (the size of smallest minimal cover < the size of best solution minimal cover) then
9: Update the best solution. 10: Update the iteration when the best solution has improved. 11:endif
```

**Algorithm 5**Algorithm of the iteration of one layer tree evolution

The stopping criterion for the one layer tree evolution is the same as the stopping criterion for the random search. ### Complexity Estimation

Let us discuss the space and time complexity estimation for the minimal orthogonal channel resource allocation and concurrently transmitting lines grouping. The space complexity is determined by the mutually acceptable interfering line sets tree space complexity which is equal to the number of tree nodes. The space complexity for the algorithm without tree pruning is just the node number in one tree. Space complexity for the random search and GA algorithms equals the largest sum of multiple pruned trees' node numbers among multiple iterations. The time complexity consists of the tree construction time complexity and minimal set cover search algorithm time complexity over that tree. The time complexity of tree construction is the sum of the successor set creation time complexity for each node. The time complexity of successor set creation for each node is equal to \(N(C_{n})\cdot(T+1)\), where \(T\) is layer depth and \(N(C_{n})\) is the size of the candidate set. It is proportional to the size of the successor set multiplied by the time complexity of mutual interference estimation. The time complexity of mutual interference estimation is proportional to the number of lines in the set, which is equal to the node layer depth plus one. The tree construction time complexity for the algorithm without tree pruning is equal to the time complexity of one tree creation. The time complexity for the random search with tree pruning is equal to the sum of time complexities for all trees created during all iterations. The time complexity for GA is equal to the random search plus the time taken to regenerate trees after crossover and mutation. Let us now estimate the worst-case time and space complexities for the search with full tree construction, with pruned tree construction, and for greedy search (Table 2). We can represent the set of lines with a binary sequence of size \(N\), where \(N\) is the number of lines, so that \(\{1,0,0,\ldots,0\}\) is the set with line \(1\), \(\{0,1,0,\ldots,0\}\) is the set with line \(2\), \(\{1,1,1,\ldots,1\}\) is the set with all lines, and so on.