## 4 Algorithm Analysis
Subsequently, the cross-degree of \(sp(s,d)\) and \(sp^{\prime}(s,d)\) is computed, and the set \(K\) is updated (line 5). If the set \(K\) is not vacant, the algorithm proceeds into the loop (lines 6-16). A new graph \(G^{\prime}\) is subsequently constructed by eliminating all links within set \(K\) from the original graph \(G\) (lines 7-8). Within this new graph \(G^{\prime}\), an alternative backup path, denoted as \(sp^{\prime}(s,d)\), from the source s to the destination \(d\) is recomputed (line 9). If this recalculated backup path \(sp^{\prime}(s,d)\) is not vacuous, it is designated as the final backup path \(bp(s,d)\), prompting an exit from the loop (lines 10-12). In the absence of a backup path, the algorithm calls the Del_edge function to iteratively remove edges in \(K\) and recalculate the backup path (line 13). The loop is exited if an edge deletion results in the nonexistence of a backup path. If a backup path is available, the set \(K\) should be updated with the intersection of \(sp(s,d)\) and \(sp^{\prime}(s,d)\) (lines 13-15). Upon exiting the while loop, if the set of potential backup paths remains nonempty, the algorithm assigns the backup path \(sp^{\prime}(s,d)\) to the backup path \(bp(s,d)\) (lines 17-18). ```
input :Topology \(G=(V,E,W)\) output :backup path \(bp(s,d)\)
1\(K\leftarrow\emptyset,sp(s,d)\gets Dijkstra(s,d)\)
2\(sp^{\prime}(s,d)\leftarrow\emptyset\)
3 for\(s\)in\(V/\{d\}\)do
4\(sp^{\prime}(s,d)\gets sp(s,d)\)
5\(\mathrm{K}\gets sp^{\prime}(s,d)\cap sp(s,d)\)
6 while\((K\
eq\emptyset)\)do
7 delete\(K\)
8\(G^{\prime}\gets G/\{K\}\)
9 compute \(sp^{\prime}(s,d)\) in \(G^{\prime}\)
10 if\((sp^{\prime}(s,d))\
eq\emptyset\)then
11\(bp(s,d)=sp^{\prime}(s,d)\)
12 break
13
14 else
15\(sp^{\prime}(s,d)\gets Del\_edge(K,sp^{\prime}(s,d))\)
16
17 end if
18 if\(sp^{\prime}(s,d)==\emptyset\)then
19 break
20 else
21\(K=sp^{\prime}(s,d)\cap sp(s,d)\)
22
23 end if
24
25 end for
26 if\(sp^{\prime}(s,d)\
eq\emptyset\)then
27\(bp(s,d)=sp^{\prime}(s,d)\)
28 end if
29
30 end for
```

**Algorithm 3** MCD-BP Algorithm

### Algorithm Discussion

Theorem 6: _The time complexity of the MCD-BP algorithm is as follows:_

\[O(|V|-1)\times O(\log|E|+\log|E|\log|K|) \tag{11}\]

Proof: The algorithm consists of the following two primary phases: topological node traversal and iterative cross-degree computation between link sets. Phase 1: Topological Node Traversal

In the first phase, the algorithm traverses all nodes in the topology except the destination node, resulting in a straightforward time complexity of \(O(|V|-1)\), where \(|V|\) represents the total number of nodes in the network. This phase ensures that each relevant node is processed for potential path computations. Phase 2: Iterative Cross-Degree Computation

The second phase, which constitutes the core of the algorithm, involves an iterative process to compute the cross-degree between link sets. Before the iterative cycle begins, potential backup paths are pre-computed, contributing a logarithmic factor of \(O(\log|E|)\), where \(|E|\) denotes the number of edges in the network. The efficiency of this phase depends on the number of iterations required to determine the optimal backup path. In the best case scenario, the algorithm identifies the desired path in the first iteration, minimizing computational overhead. However, in the worst case, it must examine all links in the cross set, leading to an additional logarithmic term \(O(\log|E|\log|K|)\), where \(|K|\) represents the size of the cross set. Consequently, the average time complexity of this phase is expressed as \(O(|V|-1)\times O(\log|E|+\log|E|\log|K|)\). Combining both phases, the overall time complexity of the MCD-BP algorithm remains dominated by the second phase due to its iterative and logarithmic dependencies. This analysis highlights the algorithm's efficiency in typical scenarios while acknowledging its worst-case behavior when extensive link evaluations are required. The logarithmic terms suggest that the algorithm scales well with increasing network size.