Dynamically Maintaining Shortest Path Trees under Batches of Updates

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

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Fully Dynamic 2-Hop Cover Labeling, Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates, Path-Fault-Tolerant Approximate Shortest-Path Trees

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