Incremental DFS algorithms: a theoretical and experimental study

MaRDI QIDQ4607876zbMATH OpenFDO

Authors Surender Baswana, Ayush Goel, Shahbaz Khan

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1705.02613, http://dl.acm.org/citation.cfm?id=3175270

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• An improved algorithm for incremental DFS tree in undirected graphs
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• On Dynamic DFS Tree in Directed Graphs
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier

Cited in

(7)

• Fault tolerant depth first search in undirected graphs: simple yet efficient
• Space-efficient fully dynamic DFS in undirected graphs
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• An improved algorithm for incremental DFS tree in undirected graphs
• Fully dynamic connectivity oracles under general vertex updates
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs

This page was built for publication: Incremental DFS algorithms: a theoretical and experimental study

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607876)