Space-efficient fully dynamic DFS in undirected graphs

DOI10.3390/A12030052MaRDI QIDQ2312405zbMATH OpenOpenAlexFDO

Authors Kengo Nakamura, Kunihiko Sadakane

Publication date 8 July 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a12030052

zbMATH Keywords

2-edge-connectivitybiconnectivitydepth-first searchdynamic graph

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• An improved algorithm for incremental DFS tree in undirected graphs
• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster

Cites work

• A data structure for dynamic trees
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• An improved algorithm for incremental DFS tree in undirected graphs
• Dynamic connectivity: connecting to networks and geometry
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Dynamically switching vertices in planar graphs
• Fast construction of wavelet trees
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• Improved data structures for the orthogonal range successor problem
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• Incremental DFS algorithms: a theoretical and experimental study
• On Dynamic DFS Tree in Directed Graphs
• Range predecessor and Lempel-Ziv parsing
• 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

(12)

• Fault tolerant depth first search in undirected graphs: simple yet efficient
• Dynamic subtrees queries revisited: the depth first tour tree
• On Dynamic DFS Tree in Directed Graphs
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• scientific article; zbMATH DE number 1798166 (Why is no real title available?)
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• Indexing graph search trees and applications
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• A Snap-Stabilizing DFS with a Lower Space Requirement
• Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries

This page was built for publication: Space-efficient fully dynamic DFS in undirected graphs

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