Semi-dynamic breadth-first search in digraphs
From MaRDI portal
Publication:1589436
DOI10.1016/S0304-3975(99)00132-2zbMath0952.68106WikidataQ127061336 ScholiaQ127061336MaRDI QIDQ1589436
Roberto Giaccio, Daniele Frigioni, Paolo Giulio Franciosa
Publication date: 12 December 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00132-2
shortest paths; incremental algorithms; amortized analysis; breadth-first search tree; decremental algorithms
68R10: Graph theory (including graph drawing) in computer science
Related Items
Lifelong planning \(\text{A}^*\), Semi-dynamic breadth-first search in digraphs, On Dynamic DFS Tree in Directed Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- The incremental maintenance of a depth-first-search tree in directed acyclic graphs
- Dynamic algorithms for shortest paths in planar graphs
- Recognizing breadth-first search trees in linear time
- Semidynamic algorithms for maintaining single-source shortest path trees
- Parallel concepts in graph theory
- On the computational complexity of dynamic graph problems
- Semi-dynamic breadth-first search in digraphs
- Maintaining a topological order under edge insertions
- Faster algorithms for the shortest path problem
- Amortized Computational Complexity
- A Separator Theorem for Planar Graphs
- An On-Line Edge-Deletion Problem
- Incremental algorithms for minimal length paths
- Shortest path queries in digraphs of small treewidth
- Fibonacci heaps and their uses in improved network optimization algorithms
- Faster shortest-path algorithms for planar graphs
