The incremental maintenance of a depth-first-search tree in directed acyclic graphs

DOI10.1016/S0020-0190(96)00202-5MaRDI QIDQ286984zbMATH OpenFDO

Authors Giorgio Gambosi, Umberto Nanni, Paolo G. Franciosa

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

analysis of algorithmsdepth-first search treedesign of algorithms

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 42967 (Why is no real title available?)
• A topological approach to dynamic graph connectivity
• An observation on time-storage trade off
• Complete problems for deterministic polynomial time
• Depth-First Search and Linear Graph Algorithms
• Depth-first search is inherently sequential
• On the computational power of pushdown automata

Cited in

(17)

• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• An improved algorithm for incremental DFS tree in undirected graphs
• Semi-dynamic breadth-first search in digraphs
• Incremental algorithm for maintaining a DFS tree for undirected graphs
• Incremental low-high orders of directed graphs and applications
• Space-efficient fully dynamic DFS in undirected graphs
• scientific article; zbMATH DE number 7561709 (Why is no real title available?)
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• Notes on oriented depth-first search and longest paths
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Incremental dead state detection in logarithmic time
• The complexity of certain incremental code generation problems
• On Dynamic DFS Tree in Directed Graphs
• Simple DFS on the complement of a graph and on partially complemented digraphs
• Depth-first discovery algorithm for incremental topological sorting of directed acyclic graphs
• Incremental DFS algorithms: a theoretical and experimental study
• Fault tolerant depth first search in undirected graphs: simple yet efficient

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)