# Space-Efficient Fully Dynamic DFS
## 7 More Space-Efficient Dynamic DFS
### Amortized Update Time Dynamic DFS
In this way their \(x\)- and \(y\)-coordinates are swapped, and finally they are in the upper triangular part of \(\mathcal{G}_{t}\). In these processes, things get complicated since their \(x\)-coordinates are stored implicitly in \(M_{t}^{\prime}\) and \(M_{t}^{\prime\prime}\) while \(y\)-coordinates are explicitly stored in \(S_{t}^{\prime}\) and \(S_{t}^{\prime\prime}\), but we manage to perform two counting sortings by this coordinate swapping method. ```
1:\(i\gets 0\), create \(S_{t}^{\prime\prime}[1...m_{t}]\) and \(M_{t}^{\prime\prime}[0...n_{t}]\) with all elem. 0
2:for\(k:=1\) to \(m_{t}\)do
3:while\(M_{t}^{\prime\prime}[i+1]<k\)do\(\operatorname{inc}(i)\)
4:\(\operatorname{inc}(M_{t}^{\prime\prime}[\min\{N[i],N[S_{t}^{\prime}[k]]\})\)
5:endfor
6:for\(l:=1\) to \(n_{t}\)do\(M_{t}^{\prime\prime}[l]\gets M_{t}^{\prime\prime}[l]+M_{t}^{\prime\prime}[l-1]\)
7:\(i\gets n_{t}\)
8:for\(k:=m_{t}\) downto 1 do
9:while\(M_{t}^{\prime\prime}[i]\geq k\)do\(\operatorname{dec}(i)\)
10:\(\operatorname{dec}(M_{t}^{\prime\prime}[\min\{N[i],N[S_{t}^{\prime}[k]]\}))\)
11:endfor
12:destroy \(S_{t}^{\prime}\) and \(M_{t}^{\prime}\), create \(S_{t}[1...m_{t}]\) and \(M_{t}[0...n_{t}]\) with all elem. 0
13:for\(k:=1\) to \(m_{t}\)do\(\operatorname{inc}(M_{t}[S_{t}^{\prime\prime}[k]])\)
14:for\(l:=1\) to \(n_{t}\)do\(M_{t}[l]\gets M_{t}[l]+M_{t}[l-1]\)
15:\(i\gets n_{t}\)
16:for\(k:=m_{t}\) downto 1 do
17:while\(M_{t}^{\prime\prime}[i]\geq k\)do\(\operatorname{dec}(i)\)
18:\(S_{t}[M_{t}[S_{t}^{\prime\prime}[k]]\gets i\)
19:\(\operatorname{dec}(M_{t}[S_{t}^{\prime\prime}[k]])\)
20:\(\operatorname{dec}(M_{t}[S_{t}^{\prime\prime}[k]])\)
21:endfor
22:destroy \(S_{t}^{\prime\prime}\) and \(M_{t}^{\prime\prime}\)
```  
**Algorithm 3** Creating \(S_{t}[1...m_{t}]\) and \(M_{t}[0...n_{t}]\) from \(S_{t}^{\prime}[1...m_{t}]\) and \(M_{t}^{\prime}[0...n_{t}]\)  
Finally, we consider the time complexity and the required space of this building process. In this analysis we write \(n_{j},m_{j}\) as simply \(n,m\) since from (b), the number of edges is changed by only \(o(m_{j})\) during phase \(j\) when \(n_{j}=o(m_{j})\). The whole process to rebuild data structures takes \(O(m\sqrt{\log n})\) time, since building single wavelet tree takes \(O(m\sqrt{\log n})\) time and the others take only \(O(m)\) time. In the whole process, data structures or arrays which take \((m+o(m))\log n\) bits are \(\mathcal{W}_{j}\), \(S_{j}\), \(S_{j+1}^{\prime}\), \(S_{j+1}^{\prime\prime}\), \(S_{j+1}\) and \(\mathcal{W}_{j+1}\), and at any time, this algorithm retains at most two of them. The working space for constructing wavelet tree in \(O(m\sqrt{\log n})\) time [18] is at most \(O(m\sqrt{\log m})\) bits. This can be written as \(O(m/\sqrt{\log m})\cdot\log n=o(m)\log n\). Here the integer sequence \(S\) has \(m\) elements and \(n\) symbols (\([0,n-1]\)). Since we assume \(n=o(m)\) as in Section 2, the pointers to form a complete binary tree shape of the wavelet tree for \(S\) requires only \(O(n\log m)=o(m)\log n\) bits, which is negligible. All other data take only \(o(m)\log n\) bits, and thus the space required by the algorithm is \((2m+o(m))\log n\) bits. Combining these observations with Lemma 2 yields the following theorems. Theorem 2 proposes the incremental DFS algorithm, while Theorem 3 states the fully dynamic one. Theorem 2: _There exists an algorithm such that given an undirected graph \(G\) and its DFS tree \(T\), for any on-line sequence of edge insertions on \(G\), a new DFS tree after each insertion can be built in amortized \(O(n\log n)\) time per update, with \(O(m\sqrt{\log n})\) preprocessing time. This algorithm requires only \((2m+o(m))\log n\) bits once data structures for the original graph are built._  
Theorem 3: _There exists an algorithm such that given an undirected graph \(G\) and its DFS tree \(T\), for any on-line sequence of graph updates on \(G\), a new DFS tree after each update can be built in amortized \(O(\sqrt{mn}\log^{1.25}n)\) time per update under fully dynamic setting, with \(O(m\sqrt{\log n})\) preprocessing time.