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

DOI10.1007/978-3-319-53925-6_23zbMath1485.68193OpenAlexW2587822263MaRDI QIDQ2980917

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

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

Related Items (5)

Unnamed Item ⋮ Unnamed Item ⋮ Space-efficient fully dynamic DFS in undirected graphs ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Fully Dynamic Connectivity Oracles under General Vertex Updates

Cites Work

• Unnamed Item
• Unnamed Item
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs
• Fast construction of wavelet trees
• A data structure for dynamic trees
• Wavelet trees for all
• Fully Functional Static and Dynamic Succinct Trees
• On Dynamic DFS Tree in Directed Graphs
• Self-indexing Based on LZ77
• Dynamic DFS in Undirected Graphs: breaking the O(m) barrier
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs

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