Fault tolerant depth first search in undirected graphs: simple yet efficient
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.
- A data structure for dynamic trees
- A nearly optimal oracle for avoiding failed vertices and edges
- An improved algorithm for incremental DFS tree in undirected graphs
- Depth-First Search and Linear Graph Algorithms
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Dynamic subgraph connectivity with geometric applications
- Dynamically switching vertices in planar graphs
- Faster randomized worst-case update time for dynamic subgraph connectivity
- Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
- Fault tolerant spanners for general graphs
- Fractional cascading. I: A data structuring technique
- scientific article; zbMATH DE number 2079421 (Why is no real title available?)
- Incremental algorithm for maintaining a DFS tree for undirected graphs
- Incremental DFS algorithms: a theoretical and experimental study
- On Dynamic DFS Tree in Directed Graphs
- Oracles for Distances Avoiding a Failed Node or Link
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- Parallel Depth-First Search in General Directed Graphs
- Space-efficient fully dynamic DFS in undirected graphs
- The incremental maintenance of a depth-first-search tree in directed acyclic graphs
This page was built for publication: Fault tolerant depth first search in undirected graphs: simple yet efficient
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149103)
