Fault tolerant depth first search in undirected graphs: simple yet efficient (Q2149103)

The paper adresses the problem of computing a depth-first search tree in a graph \(G-\mathcal{F}\), i.e. a graph \(G\) from which a set \(\mathcal{F}\) of elements (containing edges and/or vertices) has been removed. In other words, the goal is to provide a DFS tree of \(G\), even in case of failures (corresponding to \(\mathcal{F}\)). The paper presents an algorithm that solves the problem, which is (as claimed by the authors) ``drastically simpler'', conceptually and implemention-wise, than the previously existing algorithms, while competitive in terms of running time. Although claimed to be simple, the technical contents and description of the above-mentioned algorithm are roughly 15 pages long. It should be mentioned, however, that the authors took special care of motivating the problem, summarizing the main results and positioning their own contribution during the first five pages of the paper (Section 1) in a way I found very convincing. All in all, thanks to the authors, Sections 1 and 2 can be easily understood by the interested reader, while it takes more attention to follow the remainder of the paper (technical contents), which is, however, well described and illustrated.