# A Simple Approach to Dynamic Optimisation of Flexible Optical Networks with Practical Application
## 5 A Fast Heuristic Solution  
Assuming the need for a FON configuration supporting a given value of \(m\), a fast heuristic for DRP-FON is constructed as follows:  
Define the _hop matrix_, \(H\), as \(H=(h_{ij})\) where \(\forall ij\), \(h_{ij}=|a\): link \(a\) is in the shortest path between \(i\) and \(j|\) (the length of the shortest path, in hops, between nodes \(i\) and \(j\)) (\(h_{16}=4\) in Figure 1, for example). The first subroutine, using [PERSON]'s Shortest Path Algorithm[18] (or similar)[24], is then:  
\begin{tabular}{l} AlgH (Calculate the hop matrix): \\ \(\forall\ ij\), run _DSPA_ to calculate _H = (\(h_{ij}\))_ \\ \end{tabular}  
(Note that DSPA only runs _once_ to calculate each row of the matrix, \(H\), _not_ individually for each element, \(h_{ij}\).)  
The second subroutine calculates the _viability matrix_, \(V=(v_{ij})\), defined by the existence of a path between each node pair satisfying \(m\). For each \(ij\) pair, \(v_{ij}=T\) if the hop count between \(i\) and \(j\) is, at most, \(m\), or a sequence of relays can be found between \(i\) and \(j\) with the hop count of each step between, at most, \(m\) relays.  
\begin{tabular}{l} AlgV (Calculate the viability matrix): \\ \(\forall\ ij\), set \(v_{ij}=T\) if (\(h_{ij}\leq m\)) \(\vee\) (\(\exists\ k\)... \(1\),... s.t. (\(r_{k}\wedge\ldots\)... \(\wedge\ r_{1}=T\)) \\ \(\wedge\) (\(h_{ik}\leq m\) \(\wedge\)... \(\wedge\) \(h_{lj}\leq m\))); \\ \(v_{ij}=F\) otherwise \\ \end{tabular}  
With this definition, we may now revisit the NP-completeness theorem:  
**Theorem**.: _DRP-FON is NP-Complete._  
Proof.: DRP-FON is NP-hard since, for \(m=1\), it reduces to the 'Minimum Dominating Set' (MDS)[15].  
A certificate for DRP-FON can be verified in polynomial time by the following algorithm:  
\begin{tabular}{l} run AlgH \\ run AlgV \\ if \(v_{ij}=T\)\(\forall\ ij\) then \\ certificate valid \\ else \\ certificate invalid \\ \end{tabular}  
Since DRP-FON is NP-hard and has polynomial time certificate verifiability, it is NP-complete. \(\square\)  
Returning to the solution, the complete algorithm starts by initialising all relays to be switched off (unpowered), then uses a greedy (limited local search) heuristic to switch relays on (power), one at a time. The relay to be newly powered is that which has a viable path (i.e., with or without intermediate relays), of a length no greater than \(m\), to the largest number of other nodes, _not_ currently acting as relays--thus, maximising the number of _new_ nodes that are'reached/spanned' by the extra relay. The algorithm terminates when the overall solution becomes viable, i.e., when paths between all node pairs (with or without intermediate relays) are viable. This includes the special case that the initial solution is viable without any relays.  
AlqR (Optimise the relay array): // DRP-FON-heuristic set\(r_{k}\) = \(F\)\(\forall\)\(k\) // All relays switched off run AlgH // Calculate hop lengths run Algv // Calculate viable paths while\(\exists\)\(ij\) s.t. \(v_{ij}\) = \(F\)do // if more relays needed { find \(k\) s.t. |{\(i\): (\(v_{ik}\) = \(T\)) \(\wedge\) (\(r_{i}\) = \(F\))}| // Find relay that \(\geq\) |{\(i\): (\(v_{ij}\) = \(T\)) \(\wedge\) (\(r_{i}\) = \(F\))}| \(\forall\)\(j\) //... reaches most nodes set\(r_{k}\) = \(T\) // Power this new relay run Algv } // Recalculate viable paths  
Note, once more, that the relays need not form a connected network. The DRP-FON heuristic, AlgR, can be considered an extension of the greedy 'ADD' algorithm in [16] with the maximal metric for relay selection extended to include those nodes within a 'radius' of \(m\) from each candidate location.