# A Relative Coordinate-Based Topology Shaping Method for UAV Swarm with Low Computational Complexity
## 4 The Optimal Coordinate Mapping from Initial Topology to Target Topology
First, suppose the minimum value in the row \(i\) is \(c_{ij}\), then perform the inverse column reduction, i.e., add \(c_{ij}\) to all elements in column \(j\). After that, subtract \(c_{ij}\) from all elements in row \(i\), as shown in Algorithm 2 (from line 13 to line 16). 3. Augmenting row reduction, trying to find a set of alternate paths. Starting from an unassigned row \(i\), i.e., a node in initial topology, attempt to find the alternate path by first finding the current minimum value of \(c_{ij}\) in row \(i\), and then finding the second minimum value \(c_{il}\), where \(c_{il}\geq c_{ij}\). Next, reduce all elements of row \(i\) by \(c_{il}\). If \(c_{il}>c_{ij}\), the new \(c_{ij}\) is negative. Assign \(i\) to column \(j\) with the reverse column reduction for column \(j\). If column \(j\) has previously been assigned to row \(m\), repeat this step from row \(m\). This repeats until either row \(m\) is matched to an unassigned column, or it becomes impossible to transfer reduction to the selected row \(m\). This process is shown in Algorithm 2 (from line 18 to line 32). 2. The augmentation phase, which is the core of the algorithm to construct a bijective graph. For each unassigned row, the augmentation phase will find a shortest alternate path to the unassigned column through a modified [PERSON]'s algorithm. Starting with an unassigned row \(i\), the search returns a shortest path to column \(j\). If column \(j\) is assigned to row \(k\), then add row \(k\) to the path. If the distances via row \(k\) to any given column are shorter, update these distances. After augmentation, all assignments correspond to the minimum value of each row in the cost matrix, which finally leads to the assignment with the lowest weight, i.e., the minimum global energy consumption. The assignment is the mapping relationship from the initial topology coordinates to the target topology coordinates. This process is shown in Algorithm 3. ```
Input: Cost matrix \(\mathbf{C}\), Number of nodes \(N\). Output: Mapping relationship \(\mathbf{M}_{o}=[M[i,1]]_{N\times 1}\), Minimum cost \(c\). 1// The Initialization Phase
2// Column reduction
3 for\(j=N\) to \(1\)do
4\(c_{j}=j\); \(h=c_{1}\); \(i_{1}=1\);
5 for\(i=2\) to \(N\)do
6 if\(c_{ij}<h\)then
7\(h=c_{ij}\); \(i_{1}=i\); \(v_{j}=h\);
8 if\(x_{i_{1}}=0\)then
9\(x_{i_{1}}=j\); \(y_{j}=i_{1}\);
10 else
11\(x_{i}=-x_{i}\); \(y_{j}=0\);
12 // Reduction transfer
13 for each assigned row \(i\), \(i=1,2,3...N\)do
14\(j_{1}=x_{i}\);
15\(\mu=min\{c_{ij}-v_{j}:j=1,2,3...N\); \(j\
eq j_{1}\}\);
16\(v_{j1}=v_{j1}-(\mu-u_{i})\); \(u_{i}=\mu\);
17 // Augmenting row reduction
18 list = all unassigned rows;
19 for\(i\) in listdo
20 while\(u_{1}\
eq u_{2}\) or \(k\
eq 0\)do
21\(u_{1}=min\{c_{ij}-v_{j},j=1,2,3...N\); };
22 select \(j_{1}\) with \(c_{ij_{1}}-v_{j1}=u_{1}\);
23\(u_{2}=min\{c_{ij}-v_{j},j=1,2,3...N\); \(j\
eq j_{1}\}\);
24 select \(j_{2}\) with \(c_{ij_{2}}-v_{j2}=u_{2}\) and \(j_{2}\
eq j_{1}\);
25\(u_{i}=u_{2}\);
26 if\(u_{1}<u_{2}\)then
27\(v_{j_{1}}=v_{j_{1}}-(u_{2}-u_{1})\);
28
29 elseif\(j_{1}\) is assignedthen
30\(j_{1}=j_{2}\);
31\(k=y_{j_{1}}\);
32 if\(k>0\)then
33\(x_{k}=0\); \(x_{i}=j_{1}\); \(y_{j_{1}}=i\); \(i=k\);
```  
**Algorithm 2**Optimal Mapping Through Linear Assignment  
For a more intuitive understanding of the LAPIV algorithm, an example of a step-by-step initialization process is provided. Consider a cost matrix \(\mathbf{C}\) given in Figure 1(a), which is a cost matrix of a four-node UAV swarm. The minimum element in the columns is 2, 4, 3, 5 respectively. The result of column reduction is shown in Figure 1(b), in which each column reduces by its minimum element from right to left. Row 1 and column 4 are unassigned. Row 2 is assigned to column 1, row 3 is assigned to column 3, and row 4 is assigned to column 2. Reduction transfer is the following step of initialization.