## 6 Correctness Proof  
Section 5 shows that our algorithm has a linear time \(\mathcal{O}(n)\) while the upper bound of exploration under interruption is \(\mathcal{O}(n^{2})\). Now we prove that our proposal satisfies the DFORE's restrictions. Reconnaissance must satisfy the following restriction: \(\forall r\in R_{r}|\mathit{Tstamp_{t}(r)-\mathit{Tstart}}|\leq T_{expMax}\) (see Section 4.4). The maximum reconnaissance time for any given DFG \(G_{h}\) where \(i\in\mathbb{N}\) under interruptibility is \(n_{h}^{2}\). This is the time needed to explore the graph using DFS [17]. If the reconnaissance time of our proposed algorithm is greater than \(n_{h}^{2}\), then it is not better than DFS, and therefore, our proposed algorithm does not satisfy the restriction of the DFORE problem. For this particular proof, we define the reconnaissance time of our algorithm as the sum of the differences between each stamp of a region with respect to the start time \(\mathit{Tstart}\), in other words, the time taken by our algorithm to stamp every region in \(G_{h}\). By definition, the stamping time at time \(t\) is equal to: \(\mathit{Tstamp_{t}(r)=\mathit{Tstamp_{t-1}(r^{\prime})+t}}\) where \(r\
eq r^{\prime}\) and \(\mathit{Tstamp_{0}(\zeta)=\mathit{Tstart}}\).  
Definition 4: For a DFG \(G_{h}\) the number of nodes is \(n_{h}=3h^{2}-3h+1\); therefore, the reconnaissance time \(T_{expMax}\) is equal to:  
\[T_{expMax}=(3h^{2}-3h+1)^{2}. \tag{11}\]  
The following restriction should be satisfied:  
**Restriction 5**.: _The reconnaissance time of our algorithm \(T_{expAlgorithm}\) is less than the maximum reconnaissance time: \(T_{expAlgorithm}<T_{expMax}\)._  
In order to satisfy Restriction 5, the whole area should be explored within the given time \(T_{expMax}\). Therefore, both the best and general case must be analyzed. The following theorems state that our algorithm satisfies Restriction 5.  
Theorem 1: _The divide and conquer reconnaissance algorithm for the best case satisfies Restriction 5 for any given DFG \(G_{h}\)._  
Theorem 2: _The reconnaissance algorithm for the general case satisfies Restriction 5 for any given DFG \(G_{h}\)._  
To prove Theorem 1, the time taken by the reconnaissance step and the time to sample the entire area are calculated. According to Definition 4, the reconnaissance time for any given DFG \(G_{h}\) is \(T_{expMax}=(3h^{2}-3h+1)^{2}\). The time it takes to explore \(G_{h}\) is calculated using the divide and conquer method \(T_{expDivide}\) which is equal to \(T_{expAlgorithm}\). We know that \(T_{expDivide}=2e_{h}p_{h}\) (see Section 5.1). The depth of any given DFG \(G_{h}\) where \(h\in\mathbb{N}\) is \(p_{h}=2h-1\). Therefore, \(T_{expDivide}=2(e_{h})^{2}\). To prove that \(T_{expMax}>T_{expDivide}\), analyzing the inequality:  
\[(3h^{2}-3h+1)^{2}>2(e_{h})^{2} \tag{12}\]  
\[(9h^{4}-18h^{3}+15h^{2}-6h+1)>(8h^{2}-8h+2) \tag{13}\]  
The inequation holds if the DFG is greater than one; therefore, \(T_{expMax}>T_{expDivide}\) if \(h>1\).  
Now, the general case for Theorem 2 is proven. Based on the analysis, the average number of trips is \(T_{h}=3h^{2}-3h+1\). Since every trip takes \(2\epsilon_{h}\) of steps, the average reconnaissance time \(T_{expAlgorithm}\) is: \(2T_{h}\epsilon_{h}\). It is necessary to verify that \(T_{expAlgorithm}<T_{expMax}\):  
\[\begin{split} T_{expMax}>T_{expAlgorithm}\\ 2(T_{h})^{2}>2T_{h}\epsilon_{h}\\ T_{h}>\epsilon_{h}\\ 3h^{2}-3h+1>^{2}(2h-1)\\ 3h^{2}-3h+1>^{4}h-2\\ T_{expMax}>T_{expAlgorithm}|h>2\end{split} \tag{14}\]  
We have proved that both the best and the general case of our algorithm, for any given DFG, satisfies DFORE's restrictions. In the following section, our theoretical results are compared with the experimental values.