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

DOI10.1007/S00453-022-00947-7MaRDI QIDQ2149103zbMATH OpenOpenAlexFDO

Authors Surender Baswana, Ayush Tulsyan, S. K. Gupta

Publication date 28 June 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-022-00947-7

zbMATH Keywords

fault tolerancedepth-first search tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Fault tolerant reachability for directed graphs
• An improved algorithm for incremental DFS tree in undirected graphs
• A new distributed depth-first-search algorithm
• Path-based depth-first search for strong and biconnected components

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 7561709 (Why is no real title available?)
• 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 spanners for general graphs
• Fractional cascading. I: A data structuring technique
• Incremental DFS algorithms: a theoretical and experimental study
• Incremental algorithm for maintaining a DFS tree for undirected graphs
• 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)