A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs

DOI10.1007/978-3-319-53925-6_23MaRDI QIDQ2980917zbMATH OpenOpenAlexFDO

Authors Kengo Nakamura, Kunihiko Sadakane

Publication date 5 May 2017

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-53925-6_23

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Recommendations

• Space-efficient fully dynamic DFS in undirected graphs
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
• On Dynamic DFS Tree in Directed Graphs
• An improved algorithm for incremental DFS tree in undirected graphs
• Space efficient linear time algorithms for BFS, DFS and applications
• Dynamic algorithms for graphs of bounded treewidth
• Dynamic algorithms for graphs of bounded treewidth
• Dynamic graph stream algorithms in \(o(n)\) space

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• A data structure for dynamic trees
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Fast construction of wavelet trees
• Fully functional static and dynamic succinct trees
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• On Dynamic DFS Tree in Directed Graphs
• Self-indexing based on LZ77
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs
• Wavelet trees for all

Cited in

(9)

• scientific article; zbMATH DE number 7561709 (Why is no real title available?)
• A Snap-Stabilizing DFS with a Lower Space Requirement
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• An improved algorithm for incremental DFS tree in undirected graphs
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• Space-efficient fully dynamic DFS in undirected graphs
• scientific article; zbMATH DE number 1798166 (Why is no real title available?)
• Fully dynamic connectivity oracles under general vertex updates
• On Dynamic DFS Tree in Directed Graphs

This page was built for publication: A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs

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