The incremental maintenance of a depth-first-search tree in directed acyclic graphs
From MaRDI portal
Publication:286984
DOI10.1016/S0020-0190(96)00202-5zbMATH Open1336.68124MaRDI QIDQ286984FDOQ286984
Authors: Giorgio Gambosi, Umberto Nanni, Paolo G. Franciosa 
Publication date: 26 May 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Recommendations
- An improved algorithm for incremental DFS tree in undirected graphs
- Incremental DFS algorithms: a theoretical and experimental study
- On Dynamic DFS Tree in Directed Graphs
- Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Cites Work
- Title not available (Why is that?)
- Depth-First Search and Linear Graph Algorithms
- On the computational power of pushdown automata
- An observation on time-storage trade off
- Title not available (Why is that?)
- Depth-first search is inherently sequential
- A topological approach to dynamic graph connectivity
- Complete problems for deterministic polynomial time
Cited In (16)
- Title not available (Why is that?)
- A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
- Semi-dynamic breadth-first search in digraphs
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Notes on oriented depth-first search and longest paths
- Incremental low-high orders of directed graphs and applications
- Incremental DFS algorithms: a theoretical and experimental study
- An improved algorithm for incremental DFS tree in undirected graphs
- Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
- Simple DFS on the complement of a graph and on partially complemented digraphs
- Fault tolerant depth first search in undirected graphs: simple yet efficient
- Space-efficient fully dynamic DFS in undirected graphs
- Incremental algorithm for maintaining a DFS tree for undirected graphs
- Depth-first discovery algorithm for incremental topological sorting of directed acyclic graphs
- On Dynamic DFS Tree in Directed Graphs
- The complexity of certain incremental code generation problems
This page was built for publication: The incremental maintenance of a depth-first-search tree in directed acyclic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286984)
