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

DOI10.1016/S0020-0190(96)00202-5zbMath1336.68124MaRDI QIDQ286984

Giorgio Gambosi, Umberto Nanni, Paolo Giulio Franciosa

Publication date: 26 May 2016

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

zbMATH Keywords

analysis of algorithmsdesign of algorithmsdepth-first search tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

The complexity of certain incremental code generation problems ⋮ Fault tolerant depth first search in undirected graphs: simple yet efficient ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ On Dynamic DFS Tree in Directed Graphs ⋮ A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Space-efficient fully dynamic DFS in undirected graphs ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Semi-dynamic breadth-first search in digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Depth-first search is inherently sequential
• A topological approach to dynamic graph connectivity
• An observation on time-storage trade off
• Complete problems for deterministic polynomial time
• On the computational power of pushdown automata
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: The incremental maintenance of a depth-first-search tree in directed acyclic graphs