Dynamically Maintaining Shortest Path Trees under Batches of Updates
From MaRDI portal
Publication:2868652
DOI10.1007/978-3-319-03578-9_24zbMath1406.68071MaRDI QIDQ2868652
Guido Proietti, Stefano Leucci, Mattia D'Emidio, Daniele Frigioni, Annalisa D'Andrea
Publication date: 17 December 2013
Published in: Structural Information and Communication Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-03578-9_24
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- Unnamed Item
- A note on two problems in connexion with graphs
- Dynamic multi-level overlay graphs for shortest paths
- Semidynamic algorithms for maintaining single-source shortest path trees
- On the computational complexity of dynamic graph problems
- Speeding Up Dynamic Shortest-Path Algorithms
- Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
- Hierarchical Hub Labelings for Shortest Paths
- Fully dynamic shortest paths in digraphs with arbitrary arc weights
- An Incremental Algorithm for a Generalization of the Shortest-Path Problem
- Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
- Shortest Path Tree Computation in Dynamic Graphs
- Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm
- Maintaining shortest paths under deletions in weighted directed graphs